“CSES Problème Labyrinthe” Réponses codées

CSES Problème Labyrinthe

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string.h>
using namespace std;
 
char a[1000][1000], stack[1010101];
int visited[1000][1000], stackIndex=0;
 
int dx[4] = {-1, 0, 1, 0};
int dy[4] = { 0, -1, 0, 1 };
 
struct qnode {
	int x, y;
}queue[1010101];
 
int qindex, qend;
 
void bfs(int ex, int ey, int n, int m, int &ans) {
	int i, j;
	while (qindex < qend) {
		i = queue[qindex].x;
		j = queue[qindex++].y;
		if (i!=ex || j!=ey) {
			for (int p = 0; p < 4; p++) {
				if (i + dx[p] >= 0 && i + dx[p] < n && j + dy[p] >= 0 && j + dy[p] < m) {
					if (visited[i + dx[p]][j + dy[p]] == 0 || visited[i + dx[p]][j + dy[p]] > visited[i][j] + 1) {
						visited[i + dx[p]][j + dy[p]] = visited[i][j] + 1;
						queue[qend].x = i+dx[p];
						queue[qend++].y = j+dy[p];
					}
				}
			}
		}
		else {
			ans = visited[i][j] - 1;
			break;
		}
	}
}
 
void path(int i, int j, int sx, int sy, int n, int m) {
	while (i != sx || j != sy) {
		for (int p = 0; p < 4; p++) {
			if (i + dx[p] >= 0 && i + dx[p] < n && j + dy[p] >= 0 && j + dy[p] < m) {
				if (visited[i + dx[p]][j + dy[p]] == visited[i][j] - 1) {
					i = i + dx[p];
					j = j + dy[p];
					switch (p) {
					case 0 : stack[stackIndex--] = 'D'; break;
					case 1: stack[stackIndex--] = 'R'; break;
					case 2: stack[stackIndex--] = 'U';  break;
					case 3: stack[stackIndex--] = 'L';
					}
					break;
				}
			}
		}
	}
}
 
int main() {
	//freopen("sample_input.txt", "r", stdin);
	memset(stack, 0, sizeof(stack));
	qindex = qend = 0;
	int n, m;
	cin >> n >> m;
	int ans=-1, startx, starty, endx, endy;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];
			if (a[i][j] == '.') {
				visited[i][j] = 0;
			} else if (a[i][j] == 'A') {
				startx = i;
				starty = j;
			} else if(a[i][j]=='B'){
				endx = i;
				endy = j;
			} else {
				visited[i][j] = -1;
			}
		}
	}
 
	visited[startx][starty] = 1;
	queue[qend].x = startx;
	queue[qend++].y = starty;
	bfs(endx, endy, n, m, ans);
 
	if (ans == -1)
		cout << "NO\n";
	else {
		cout << "YES\n";
		cout << ans << "\n";
		stackIndex = ans;
		stack[stackIndex--] = '\n';
		path(endx, endy, startx, starty, n, m);
		cout << stack<<"\n";
	}
	return 0;
}