自己花了两个多小时想的代码,过了3/10个数据 时间超限
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=120;
char path[N][N];
bool st[N][N];
bool sign=0;
void dfs(int x,int y,int n,int a,int b)//(当前的x,当前的y,矩阵n,终点a,终点b)
{
if(sign) return; //处理多种情况 直接返回
if(x==a&&y==b) {
sign=1;
return ;
}
if(y==n||y<0||x==n||x<0) return;
if(!st[x][y+1]&&path[x][y+1]=='.') {
st[x][y+1]=true;
dfs(x,y+1,n,a,b);
st[x][y+1]=false;
}
if(y-1>=0){//注意是大于等于 不是大于
if(!st[x][y-1]&&path[x][y-1]=='.') {
st[x][y-1]=true;
dfs(x,y-1,n,a,b);
st[x][y-1]=false;
}
}
if(!st[x+1][y]&&path[x+1][y]=='.') {
st[x+1][y]=true;
dfs(x+1,y,n,a,b);
st[x+1][y]=false;
}
if(x-1>=0){
if(!st[x-1][y]&&path[x-1][y]=='.') {
st[x-1][y]=true;
dfs(x-1,y,n,a,b);
st[x-1][y]=false;
}
}
}
int main(){
int k;
cin>>k;
while(k--){
sign=0;//可以同时处理两种情况
int n;
cin>>n;
for(int x=0;x<n;x++){
for(int y=0;y<n;y++){
cin>>path[x][y];
}
}
int ha,la,hb,lb;
cin>>ha>>la>>hb>>lb;
if(path[ha][la]=='#'||path[hb][lb]=='#') cout<<"NO"<<endl;
else {
dfs(ha,la,n,hb,lb);
if(sign) cout<<"YES"<<endl;//YES和NO都在main中写 更美观
else cout<<"NO"<<endl;
}
}
return 0;
}
自己本来用这段代码来输出路径调试 事实上大错特错
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(st[i][j]==true) cout<<i<<' '<<j<<endl;
}
}
这样把所有遍历过的位置全都写出来了 (那些没有来得及走到头回溯,就找到终点的点)
应该用栈来存 回溯的过程中出栈