球猪
  • 板块P1238 走迷宫
  • 楼主dtrthg
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/2/8 23:45
  • 上次更新2023/10/28 09:21:24
查看原帖
球猪
379113
dtrthg楼主2022/2/8 23:45

啊巴啊巴啊巴啊巴啊

#include <iostream>
using namespace std;
const int Maxn=15+10;
int a[Maxn][Maxn];
bool vis[Maxn][Maxn];
const int dx[]={0,1,0,-1};
const int dy[]={-1,0,1,0};
int tx,ty;
int m,n;
int ans[Maxn*Maxn][2+10];//用于储存路径 
int cnt=1;//路径的步数 
bool flag=false;//判断是否有解 
void dfs(int x,int y)
{
	if(x==tx&&y==ty)//如果到达目的地 
	{
		flag=true;//说明有解 
		for(int i=1;i<cnt;i++)//i<cnt是因为"->"原因最后一步单独输 
		{
			cout<<"("<<ans[i][1]<<","<<ans[i][2]<<")"<<"->";
		}
		cout<<"("<<ans[cnt][1]<<","<<ans[cnt][2]<<")"<<endl;
		return ;
	}
	for(int i=0;i<4;i++)
	{
		int nx=x+dx[i],ny=y+dy[i];
		if(nx>=1&&nx<=m&&ny>=1&&ny<=n)//判断是否越界 
		{
			if(vis[nx][ny]==false&&a[nx][ny]!=0)//判断走没走过且是否可以走 
			{
				cnt++;//步数++ 
				ans[cnt][1]=nx; ans[cnt][2]=ny;//计录路径 
				vis[nx][ny]=true;//标记为走过 
				dfs(nx,ny);
				vis[nx][ny]=false;
				ans[cnt][1]=0; ans[cnt][2]=0;
				cnt--;//回溯 
			}
		}
	}
}
int main()
{
	cin>>m>>n;
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>a[i][j];
		}
	}
	int sx,sy;cin>>sx>>sy;
	cin>>tx>>ty;
	vis[sx][sy]=true;//标记起点 
	ans[1][1]=sx; ans[1][2]=sy;//将起点记录于路径中 
	dfs(sx,sy);
	if(flag==false) cout<<"-1"<<endl;//如果无解 
	return 0;//不完美的结束( 
}
2022/2/8 23:45
加载中...