O labirinto de ilusão é infinito, mas é formado pela repetição de uma matriz de N linhas por M colunas. Algumas células são estradas, representadas por '.', e outras são paredes, representadas por '#'. O ponto de partida é marcado com 'S'. LHX e WD podem mover-se para cima, baixo, esquerda e direita, mas apenas para células que não sejam paredes. O objetivo é dteerminar se eles podem escapar do labirinto, o que significa alcançar uma distância infinita a partir do ponto de partida.
Análise: Se um ponto for visitado mais de uma vez durante a busca, isso indica um ciclo que permite ir para longe, então a resposta é Sim. Caso contrário, Não.
Código 1: Tentativa inicial (falha)
#include <iostream>
#include <cstring>
using namespace std;
char cell;
int rows, cols, grid[1505][1505], visits[1505][1505], dirCount[5]; // Cima, baixo, esquerda, direita
int dx[5] = {0, 0, 0, -1, 1}, dy[5] = {0, 1, -1, 0, 0};
void printGrid() {
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) {
cout << visits[i][j];
}
cout << endl;
}
cout << endl;
}
void dfs(int startX, int startY) {
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
int flagX = 0, flagY = 0;
int a = startX + dx[i], b = startY + dy[j];
if (a > rows) a -= rows, ++dirCount[2], flagX = 2;
if (a < 1) a += rows, ++dirCount[1], flagX = 1;
if (b > cols) b -= cols, ++dirCount[4], flagY = 4;
if (b < 1) b += cols, ++dirCount[3], flagY = 3;
if (grid[a][b] != 0) {
++visits[a][b];
if (visits[a][b] == 2) {
if (((dirCount[1] % 2 == 1 && dirCount[1] != 0) || dirCount[1] == 0) &&
((dirCount[2] % 2 == 1 && dirCount[2] != 0) || dirCount[2] == 0) &&
((dirCount[3] % 2 == 1 && dirCount[3] != 0) || dirCount[3] == 0) &&
((dirCount[4] % 2 == 1 && dirCount[4] != 0) || dirCount[4] == 0)) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
return;
} else {
dfs(a, b);
--visits[a][b];
}
} else {
--dirCount[flagX];
--dirCount[flagY];
}
}
}
}
int main() {
while (cin >> rows >> cols) {
int startX, startY;
memset(dirCount, 0, sizeof(dirCount));
memset(grid, 0, sizeof(grid));
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) {
cin >> cell;
if (cell != '#') grid[i][j] = 1;
if (cell == 'S') startX = i, startY = j;
}
}
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) cout << grid[i][j] << " ";
cout << endl;
}
cout << endl;
dfs(startX, startY);
}
return 0;
}
Código 2: 90% correto, último caso de teste traiçoeiro
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 1510;
int rows, cols, grid[MAXN][MAXN], startX, startY, visited[MAXN][MAXN], visitX[MAXN][MAXN], visitY[MAXN][MAXN];
int flag, dx[5] = {0, 0, 0, 1, -1}, dy[5] = {0, 1, -1, 0, 0};
char ch;
inline int readInt() {
int s = 0, w = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * w;
}
void dfs(int x, int y, int numX, int numY) {
if (flag) return;
if (visited[x][y] && (visitX[x][y] != numX || visitY[x][y] != numY)) {
flag = 1;
return;
}
visited[x][y] = 1;
visitX[x][y] = numX;
visitY[x][y] = numY;
for (int i = 1; i <= 4; i++) {
int xi = (x + dx[i] + rows) % rows;
int yi = (y + dy[i] + cols) % cols;
int xii = numX + dx[i];
int yii = numY + dy[i];
if (!grid[xi][yi] && (!visited[xi][yi] || visitX[xi][yi] != xii || visitY[xi][yi] != yii))
dfs(xi, yi, xii, yii);
}
}
int main() {
while (~scanf("%d%d", &rows, &cols)) {
flag = 0;
memset(visited, 0, sizeof(visited));
memset(grid, 0, sizeof(grid));
memset(visitX, 0, sizeof(visitX));
memset(visitY, 0, sizeof(visitY));
ch = getchar();
ch = getchar();
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
ch = getchar();
cin >> ch;
if (ch == '#') grid[i][j] = 1;
if (ch == 'S') startX = i, startY = j;
}
ch = getchar();
ch = getchar();
}
dfs(startX, startY, startX, startY);
if (flag) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}
Código 3: Correto
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 1510;
int rows, cols, grid[MAXN][MAXN], startX, startY, visited[MAXN][MAXN], visitX[MAXN][MAXN], visitY[MAXN][MAXN];
int flag, dx[5] = {0, 0, 0, 1, -1}, dy[5] = {0, 1, -1, 0, 0};
char ch;
inline int readInt() {
int s = 0, w = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * w;
}
void dfs(int x, int y, int numX, int numY) {
if (flag) return;
if (visited[x][y] && (visitX[x][y] != numX || visitY[x][y] != numY)) {
flag = 1;
return;
}
visited[x][y] = 1;
visitX[x][y] = numX;
visitY[x][y] = numY;
for (int i = 1; i <= 4; i++) {
int xi = (x + dx[i] + rows) % rows;
int yi = (y + dy[i] + cols) % cols;
int xii = numX + dx[i];
int yii = numY + dy[i];
if (!grid[xi][yi] && (!visited[xi][yi] || visitX[xi][yi] != xii || visitY[xi][yi] != yii))
dfs(xi, yi, xii, yii);
}
}
int main() {
while (~scanf("%d%d", &rows, &cols)) {
flag = 0;
memset(visited, 0, sizeof(visited));
memset(grid, 0, sizeof(grid));
memset(visitX, 0, sizeof(visitX));
memset(visitY, 0, sizeof(visitY));
ch = getchar();
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
cin >> ch;
if (ch == '#') grid[i][j] = 1;
if (ch == 'S') startX = i, startY = j;
}
}
dfs(startX, startY, startX, startY);
if (flag) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}