## 希望大家不要写dfs（除非dalao）
我以下的dfs AC\*1 TLE\*9
```cpp
#include<bits/stdc++.h>
using namespace std;
int dx[5]={0,0,0,1,-1};
int dy[5]={0,1,-1,0,0};
int n,qi,qj,zi,zj,min1=100000000,s;
int b[1005][1005];
char a[1005][1005];
bool pd(int i1,int j1){
if(i1<1 || i1>n || j1<1 || j1>n || b[i1][j1]==1 || a[i1][j1]=='1')
return false;
return true;
}
void dfs(int i,int j){
if(i==zi && j==zj){
if(s<min1)
min1=s;
}
else{
for(int k=1;k<=4;k++){
int ii=i+dx[k],jj=j+dy[k];
if(pd(ii,jj)){
b[ii][jj]=1;
s++;
dfs(ii,jj);
b[ii][jj]=0;
s--;
}
}
}
}
int main()
{
cin>>n;
for(int l=1;l<=n;l++)
scanf("%s",a[l]);
cin>>qi>>qj>>zi>>zj;
b[qi][qj]=1;
dfs(qi,qj);
cout<<min1;
return 0;
}
```
by ④纱 @ 2020-10-06 18:20:35
@[④纱](/user/231577) 重构吧
by MilkyCoffee @ 2020-10-06 18:27:44
粗略看了一眼时限，DFS连20%的数据都过不了
by MilkyCoffee @ 2020-10-06 18:28:12
要用bfs
by MilkyCoffee @ 2020-10-06 18:28:56
我的第一个就是bfs 只不过还在调
by ④纱 @ 2020-10-06 18:36:13
@[牛奶小咖啡](/user/317198) 实际上DFS+记忆化写得好看大概是能过完的(大概
by konjacq @ 2020-10-06 18:37:44
@[④纱](/user/231577) 您的DFS加个记忆化应该就能过
```cpp
#include<bits/stdc++.h>
using namespace std;
int dx[5]={0,0,0,1,-1};
int dy[5]={0,1,-1,0,0};
int n,qi,qj,zi,zj,min1=100000000,s;
int b[1005][1005];
char a[1005][1005];
bool pd(int i1,int j1){
if(i1<1 || i1>n || j1<1 || j1>n || b[i1][j1]==1 || a[i1][j1]=='1')
return false;
return true;
}
void dfs(int i,int j){
if(i==zi && j==zj){
if(s<min1)
min1=s;
}
else{
for(int k=1;k<=4;k++){
int ii=i+dx[k],jj=j+dy[k];
if(pd(ii,jj)&&b[ii][jj]>b[i][j]+1){
b[ii][jj]=b[i][j]+1;
s++;
dfs(ii,jj);
s--;
}
}
}
}
int main()
{
cin>>n;
for(int l=1;l<=n;l++) {
scanf("%s",a[l]);
memset(b,0x3f,sizeof(b));
}
cin>>qi>>qj>>zi>>zj;
b[qi][qj]=1;
dfs(qi,qj);
cout<<min1;
return 0;
}
```
by konjacq @ 2020-10-06 18:40:22
~~其实SPFA好像也行~~
by Black_Porridge @ 2020-10-06 18:42:53
# 谢谢，已AC
```cpp
#include<bits/stdc++.h>
using namespace std;
int dx[5]={0,0,0,1,-1};
int dy[5]={0,1,-1,0,0};
int n,qi,qj,zi,zj,head=0,tail=1,k;
int b[1005][1005],q[1000005][4];
char a[1005][1005];
bool pd(int i1,int jjj){
if(i1<1 || i1>n)
return false;
if(jjj<1 || jjj>n)
return false;
if(b[i1][jjj]==1)
return false;
if(a[i1][jjj]=='1')
return false;
return true;
}
void bfs(int i,int j){
do{
head++;
for(k=1;k<=4;k++){
int ii=q[head][1]+dx[k],jj=q[head][2]+dy[k];
if(pd(ii,jj)){
tail++;
b[ii][jj]=1;
q[tail][1]=ii;
q[tail][2]=jj;
q[tail][3]=q[head][3]+1;
if(ii==zi && jj==zj)
return;
}
}
}while(head<tail);
}
int main()
{
cin>>n;
for(int l=1;l<=n;l++)
scanf("%s",a[l]+1);
cin>>qi>>qj>>zi>>zj;
q[1][1]=qi;
q[1][2]=qj;
b[qi][qj]=1;
bfs(qi,qj);
cout<<q[tail][3];
return 0;
}
```
by ④纱 @ 2020-10-07 09:07:59