我看不懂网上的人写的迭代加深,只知道了有这种思想,请能帮忙具体实现吗,以下题我写的代码为例,谢谢。
P1746-link(虽然是BFS板子题)
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int n,sx,sy,ex,ey,ans=N*N+10;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
char Map[N][N];
bool vis[N][N];
void dfs(int x,int y,int dis)
{
if(x==ex&&y==ey)
{
ans=min(ans,dis);
return;
}
for(int i=0;i<4;i++)
{
int tx=x+dx[i],ty=y+dy[i];
if((tx>=1&&tx<=n&&ty>=1&&ty<=n) && Map[tx][ty]=='0' && !vis[tx][ty])
{
vis[tx][ty]=true;
dfs(tx,ty,dis+1);
vis[tx][ty]=false;
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
string s;
cin>>s;
for(int j=0;j<s.size();j++) Map[i][j+1]=s[j];
}
cin>>sx>>sy>>ex>>ey;
vis[sx][sy]=true;
dfs(sx,sy,0);
cout<<ans;
return 0;
}