80求助
  • 板块P2802 回家
  • 楼主SZnP
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/11/6 09:52
  • 上次更新2023/11/4 01:19:00
查看原帖
80求助
516867
SZnP楼主2021/11/6 09:52
#incude <bits/stdc++.h>
using namespace std;
bool ak[15][15];
int x,y,a[15][15],minn=1e9,u,o;
void DFS(int zhi,int g,int h,int step)
{
	if(step>minn||step>2*x*y)return;
	if(g>=x||h>=y)return;
	if(zhi==0)return;
	if(g==u&&h==o)
	{
		if(step<minn)minn=step;
		return;
	}
	if(a[g][h]==4)zhi=6;
	if(a[g][h+1]!=0&&ak[g][h+1]!=true)
	{
		ak[g][h+1]=true;
		DFS(zhi-1,g,h+1,step+1);
		ak[g][h+1]=false;
	}
	if(a[g][h]==4)zhi=6;
	if(a[g-1][h]!=0&&ak[g-1][h]!=true)
	{
		ak[g-1][h]=true;
		DFS(zhi-1,g-1,h,step+1);
		ak[g-1][h]=false;
	}
	if(a[g][h]==4)zhi=6;
	if(a[g][h-1]!=0&&ak[g][h-1]!=true)
	{
		ak[g][h-1]=true;
		DFS(zhi-1,g,h-1,step+1);
		ak[g][h-1]=false;
	}
	if(a[g][h]==4)zhi=6;
	if(a[g+1][h]!=0&&ak[g+1][h]!=true)
	{
		ak[g+1][h]=true;
		DFS(zhi-1,g+1,h,step+1);
		ak[g+1][h]=false;
	}
	return;
}
int main()
{
	scanf("%d%d",&x,&y);
	int i,j,z,w;
	for(i=0;i<x;i++)
	for(j=0;j<y;j++)
	{
		scanf("%d",&a[i][j]);
		if(a[i][j]==2){
			z=i;
			w=j;
		}
		if(a[i][j]==3){
			u=i;
			o=j;
		}
		ak[i][j]=false;
	}
	DFS(6,z,w,0);
	if(minn==1e9)cout<<"-1";
	else cout<<minn;
	return 0;
}
2021/11/6 09:52
加载中...