12510-HakkasMaze
unknown
c_cpp
3 years ago
2.1 kB
3
Indexable
#include <stdio.h> #include <stdlib.h> void DFS(int x, int y); int r, c; int flag = 0; int dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}}; int used[1001][1001]; char map[1001][1001]; int Tadd[2][1000001]; int main(void) { // freopen("test.txt", "r", stdin); // freopen("out.txt", "w", stdout); int n; scanf("%d", &n); while (n--) { scanf("%d %d ", &r, &c); for (int i = 0; i < r; ++i) { scanf("%s", map[i]); } for (int i = 0; i < r; ++i) { for (int j = 0; j < c; ++j) { used[i][j] = 0; } } int a = 0; for (int i = 0; i < r; ++i) { for (int j = 0; j < c; ++j) { if (map[i][j] == 'T') { Tadd[0][a] = i; Tadd[1][a] = j; a++; } } } Tadd[0][a] = -1; used[r - 1][c - 1] = 1; if (map[r - 1][c - 1] != '#') { DFS(r - 1, c - 1); } if (used[0][0]) { printf("Yes\n"); } else { printf("No\n"); } } return 0; } void DFS(int x, int y) { if (used[0][0] == 1) { return; } if (map[x][y] == 'T') { for (int i = 0;; ++i) { if (Tadd[0][i] == -1) { break; } if (used[Tadd[0][i]][Tadd[1][i]] == 0) { used[Tadd[0][i]][Tadd[1][i]] = 1; DFS(Tadd[0][i], Tadd[1][i]); } } } for (int i = 0; i < 4; ++i) { int nx, ny; nx = x + dir[i][0]; ny = y + dir[i][1]; if (nx >= 0 && nx < r && ny >= 0 && ny < c) { if ((map[nx][ny] == '*' || map[nx][ny] == 'T') && used[nx][ny] == 0) { used[nx][ny] = 1; DFS(nx, ny); } } } }
Editor is loading...