0分TLE,DFS求助
  • 板块P1238 走迷宫
  • 楼主meifan666
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/29 13:29
  • 上次更新2024/7/29 14:43:53
查看原帖
0分TLE,DFS求助
1284088
meifan666楼主2024/7/29 13:29
#include <bits/stdc++.h>
using namespace std;
int read();
bool b[20][20];
int n,m;
struct way{
	int x,y;
};
way ans[425];
bool flag;
int sx,sy,fx,fy;
void DFS(int x,int y,int sum);
int main() {
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			b[i][j]=1-read();
		}
	}
	sx=read(),sy=read();
	fx=read(),fy=read();
	DFS(sx,sy,1);
	if(flag==0)cout<<-1;
	return 0;
}
int read(){
	int k=1,ans=0;
	char s=getchar();
	while(s<'0'||s>'9')if(s=='-')k=-1,s=getchar();
	while(s>='0'&&s<='9')ans=ans*10+s-'0',s=getchar();
	return k*ans;
}
void DFS(int x,int y,int sum){
	if(x<1||x>n||y<1||y>m||b[x][y])return;
	ans[sum]=way{x,y};
	if(x==fx&&y==fy){
		flag=1;
		for(int i=1;i<=sum;i++){
			printf("(%d,%d)",ans[i].x,ans[i].y);
			if(i!=sum)printf("->");
		}
		cout<<'\n';
		return;
	}
	b[x][y]=1;
	DFS(x,y-1,sum+1);
	DFS(x-1,y,sum+1);
	DFS(x,y+1,sum+1);
	DFS(x+1,y,sum+1);
	b[x][y]=0;
	return;
}
2024/7/29 13:29
加载中...