题解：P10234 [yLCPC2024] B. 找机厅

题意简述

给你一个长 \(n\) 宽 \(m\) 的 \(01\) 迷宫，从 \((1,1)\) 开始要走到 \((n,m)\)。如果能走那么输出最短路和路径（路径用 \(L R U D\) 表示），否则输出 \(-1\) 。有 \(t\) 组数据。

如果当前格子是 \(0\) 那么你只能走到 \(1\) 的格子，反之亦然。

思路

考虑使用 \(BFS\) ，每次走到这个点时遍历四个点（即上下左右），如果可以那么加入队列讲到这个点的路径加一。

记录路径

这也算这道题的难点，我们用一个 \(fa\) 的结构体来记录当前坐标的上一个最后在输出路径。

code

#include <bits/stdc++.h>
using namespace std;
struct node {
	int x, y, time;
} fa[2005][2005];
node cu,c;
string way;
int n, m;
char mp[2005][2005];
bool used[2005][2005];
int ans[2005][2005];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
char dir[] = {'U', 'D', 'L', 'R'};
void find()
{
	way = "";
	while (cu.x != 1 || cu.y != 1) {
		c = fa[cu.x][cu.y];
		for (int i = 0; i < 4; i++) {
			if (c.x + dx[i] == cu.x && c.y + dy[i] == cu.y) {
				way += dir[i];
				break;
			}
		}
		cu = c;
	}
}
void bfs() {
	queue<node> q;
	q.push({1, 1});
	used[1][1] = true;
	ans[1][1] = 0;
	
	
	while (!q.empty()) {
		cu = q.front();
		q.pop();
		
		if (cu.x == n && cu.y == m) {
			cout << ans[cu.x][cu.y] << endl;
			
			find();
			
			for (int i = way.size() - 1; i >= 0; i--) {
				cout << way[i];
			}
			cout << endl;
			
			return;
		}
		
		for (int i = 0; i < 4; i++) {
			int tx = cu.x + dx[i];
			int ty = cu.y + dy[i];
			if (tx >= 1 && tx <= n && ty >= 1 && ty <= m && mp[cu.x][cu.y] != mp[tx][ty] && used[tx][ty]==0) {
				used[tx][ty] = 1;
				ans[tx][ty] = ans[cu.x][cu.y] + 1;
				fa[tx][ty] = {cu.x, cu.y, ans[tx][ty]};
				q.push({tx, ty});
			}
		}
	}
	
	cout << -1 << endl;
}

int main() {
	int t;
	cin >> t;
	
	for(int i=1;i<=t;i++)
	{
		cin >> n >> m;
		memset(used, false, sizeof(used));
		
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				cin >> mp[i][j];
			}
		}
		
		bfs();
	}
	return 0;
}