关于dfs迭代加深
  • 板块学术版
  • 楼主Zhang_Wenjie
  • 当前回复9
  • 已保存回复9
  • 发布时间2022/10/2 14:39
  • 上次更新2023/10/27 09:13:07
查看原帖
关于dfs迭代加深
481621
Zhang_Wenjie楼主2022/10/2 14:39

我看不懂网上的人写的迭代加深,只知道了有这种思想,请能帮忙具体实现吗,以下题我写的代码为例,谢谢。
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;
}
2022/10/2 14:39
加载中...