2WA 3RE求助(dp不会写用的dfs)
查看原帖
2WA 3RE求助(dp不会写用的dfs)
917683
rnf5114楼主2023/4/1 09:08
#include<bits/stdc++.h>
using namespace std;
char maze[100][100];
bool flag[100][100];
int dx[]={0,1,-1};
int dy[]={1,0,0};
int m,n,man,mam,w,k;
int sum=0;
void dfs(int x,int y){
	if(maze[x][y]=='T'){
		sum++;
		return ;
	}
	for(int i=0;i<3;i++){
		int nx=x+dx[i];
		int ny=y+dy[i];
		if(flag[nx][ny]==0&&maze[nx][ny]=='*'||maze[nx][ny]=='T'&&nx>0&&ny>0&&nx<m+1&&ny<n+1){
			flag[nx][ny]=1;
			dfs(nx,ny);
			flag[nx][ny]=0;
		}
	}
}
int main(){
	cin>>m>>n>>mam>>man;
	for(w=-2;w<=2;w++){
		for(k=-2;k<=2;k++){
			if(w!=0&&k!=0&&k!=w){
				if(mam+w<=m+1&&mam+w>=1&&man+k<=n+1&&man+k>=1){
					maze[w][k]='q';
				}
			}
		}
	}
	for(int i=1;i<=m+1;i++){
		for(int j=1;j<=n+1;j++){
			if(i==m+1&&j==n+1)
				maze[i][j]='T';
			if(maze[i][j]!='q')
				maze[i][j]='*';
		}
	}
	flag[1][1]=1;
	dfs(1,1);
	cout<<sum<<endl;
}
2023/4/1 09:08
加载中...