迷宫寻路[天梯赛 -- 栈]

文章目录

题目描述
思路
AC代码

题目描述

在这里插入图片描述

输入样例
8 8	
0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 0 0 1 1 0 0
0 1 1 1 0 0 0 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 0
0 1 1 1 0 1 1 0
1 0 0 0 0 0 0 0
4 4	
0 0 1 0
0 0 0 0
0 0 1 1 
0 1 0 0
-1 -1

输出样例
1,1
2,1
3,1
4,1
5,1
5,2
5,3
6,3
6,4
6,5
7,5
8,5
8,6
8,7
8,8

NO FOUND

思路

bfs

需要对每一条路径上的点进行保存（用temp数组），当找到一条更短路径时，保存其长度，用于后面的遍历中比较；当找到终点时，我们将temp数组中的结果赋值给res数组

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
int m, n, min_step;
int g[N][N];
int res[N][2], temp[N][2];
int vis[N][N];
int dir[4][2] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
bool IN(int x, int y)
{
    return x >= 1 && x <= m && y >= 1 && y <= n;
}
void dfs(int x, int y, int step)
{
	if(step > min_step) return;
	
	if(x == m && y == n)
	{
		for(int i = 0; i < N; i ++)
		{
			if(temp[i][0] == -1 && temp[i][1] == -1) break;
			res[i][0] = temp[i][0];
			res[i][1] = temp[i][1];
		}
		min_step = step;
		return;
	}
	
	for(int i = 0; i < 4; i ++)
	{
		int tx = x + dir[i][0];
        int ty = y + dir[i][1];
        if(IN(tx, ty) && g[tx][ty] == 0 && !vis[tx][ty]) 
        {
        	temp[step][0] = tx;
        	temp[step][1] = ty;
        	vis[tx][ty] = true;
        	dfs(tx, ty, step + 1);
        	vis[tx][ty] = false;
		}
	}
	return;
}
int main()
{
	while(1)
	{
		cin >> m >> n;
		if(m == -1) break;
		memset(g, -1, sizeof(g));
		memset(vis, 0, sizeof(vis));
		memset(res, -1, sizeof(res));
		memset(temp, -1, sizeof(temp));
		for(int i = 1; i <= m; i ++)
		{
			for(int j = 1; j <= n; j ++) cin >> g[i][j];
		}
		min_step = 0x3f3f3f3f;
		vis[1][1] = true;
		dfs(1, 1, 0);
		if(min_step != 0x3f3f3f3f) 
		{
			cout << "1,1" << endl;
			for(int i = 0; i < min_step; i ++) cout << res[i][0] << "," << res[i][1] << endl;
            cout << endl;
		}
		else cout << "NO FOUND" << endl;
		//cout << endl;
	}
	return 0;
}