35分求助
  • 板块P1238 走迷宫
  • 楼主DanRan02
  • 当前回复6
  • 已保存回复6
  • 发布时间2022/11/21 16:04
  • 上次更新2023/10/27 02:04:45
查看原帖
35分求助
253036
DanRan02楼主2022/11/21 16:04

#2#3#4#5#11#13#14#15#16#17#19 TLE
#12#20 WA
代码如下

#include<iostream>
#include<cstring>
#define N 20
using namespace std;
int n,m,stx,sty,edx,edy;						      //startx,starty,endx,endy
int map[N][N];					//存图
pair<int,int> Prev[N][N];		//存该坐标下一个坐标
int dx[4]={0,-1,0,1};			//优先顺序:左上右下
int dy[4]={-1,0,1,0};
int flag;						//是否有解
void dfs(int x,int y)
{
	if(x==edx && y==edy)//如果有解
	{
		flag=1;//改变标记
		int x2=stx,y2=sty;
		while(x2!=edx || y2!=edy)//输出路径过程
		{
			printf("(%d,%d)",x2,y2);
			printf("->");
			int t1=x2,t2=y2;
			x2=Prev[t1][t2].first;
			y2=Prev[t1][t2].second;
		}
		printf("(%d,%d)",edx,edy);
		cout<<endl;
		return ;//回溯
	}
	for(int i=0;i<4;i++)
	{
		int xn=x+dx[i],yn=y+dy[i];
//		cout<<xn<<"-----"<<yn<<"-----"<<endl;  调试
		if(map[xn][yn] && xn>0 && xn<=m && yn>0 && yn<=n)
		{							//符合条件则可以走
			Prev[x][y]={xn,yn};	//存储该点的下一个点的坐标
			map[xn][yn]=0;
			dfs(xn,yn);				//递归dfs
			Prev[x][y]={0,0};		//回溯
			map[xn][yn]=1;
		}
	}
}
int main()
{
	cin>>m>>n;
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>map[i][j];
		}
	}
	map[stx][sty]=0;		//初始化
	cin>>stx>>sty>>edx>>edy;
	dfs(stx,sty);
	if(!flag) cout<<"-1"<<endl;//无解输出-1
	return 0;
}
2022/11/21 16:04
加载中...