[数据结构与算法]迷宫（bfs找最短路径）

题目

#include <bits/stdc++.h>
using namespace std;

string ss;
int mp[60][60];
int vis[60][60];
int dx[] = {1,0,0,-1};
int dy[] = {0,-1,1,0};
char dir[] = {'D', 'L', 'R', 'U'};


struct node {
	int x, y;
	int step;
	string path;
	node() {} 
	node(int x_, int y_, int step_, string path_) {
		x = x_;
		y = y_;
		step = step_;
		path = path_; 
	}
};
queue<node> qq;



int main()
{
	// 请在此输入您的代码
	for (int i = 1; i <= 30; i++) {
		cin >> ss;
		for (int j = 1; j <= 50; j++) {
			mp[i][j] = ss[j-1] - '0';
		}
	}
	
	qq.push(node(1,1,0,""));
	vis[1][1] = 1;
	while (!qq.empty()) {
		node t = qq.front();
		qq.pop();
		if (t.x == 30 && t.y == 50) {
			cout << t.path;
			break;
		}
		for (int i = 0; i < 4; i++) {
			int tx = t.x + dx[i];
			int ty = t.y + dy[i];
			if (tx <= 0 || tx > 30 || ty <= 0 || ty > 50) continue;
			if (mp[tx][ty] == 0 && !vis[tx][ty]) {
				qq.push(node(tx, ty, t.step + 1, t.path + dir[i]));
				vis[tx][ty] = 1;
			} 
		}
	}
	
	
	
	
	return 0;
}