bfs 문제입니다. 원래 계속 뻗어나가는데, 뻗어나가는 단계에서, 조건이 더 들어간다는 것이 차이점 입니다. 그리고 초기화의 중요성에 대해서 다시 알수 있는 문제였습니다. 초기화 해야하는 것은 무엇인지 다시 적어봅니다. que, map, visit, ans 입니다. 그리고 보통 max 에 들어가는 변수에 대해서는 초기화를 시켜주면 됩니다. |
/* 1437탈주범 검거 bfs 보다 dfs 가 빠르므로 dfs 로 풀어야 하는가? 갔던길에 대한 체크를 해야겠습니다. */ #include <iostream> #include <queue> using namespace std; #define SIZE 55 // 51; int N, M, R, C, L; int map[SIZE][SIZE]; int visit[SIZE][SIZE]; int x, y, nx, ny, t; int dx[] = { 0,0,1,-1 }; int dy[] = { 1,-1,0,0 }; struct points { int x, y, t; }; queue<points> que; int ans; void problemIn() { cin >> N >> M >> R >> C >> L; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { cin >> map[i][j]; } } } void map_init() { for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) map[i][j] = 0; } void visit_init() { for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) visit[i][j] = 0; } void solve() { x = R; y = C; que.push({ x,y,1 }); while (1) { if (que.front().t == L + 1) break; x = que.front().x; y = que.front().y; t = que.front().t; que.pop(); visit[x][y] = 1; int d = map[x][y]; switch (d) { case 1: // 상 하 좌 우 if (y + 1 >= 0 && y + 1 < M && visit[x][y + 1] == 0 && map[x][y + 1] == 1 || map[x][y + 1] == 3 || map[x][y + 1] == 6 || map[x][y + 1] == 7) que.push({ x,y + 1, t + 1 }); if (y - 1 >= 0 && y - 1 < M && visit[x][y - 1] == 0 && map[x][y - 1] == 1 || map[x][y - 1] == 3 || map[x][y - 1] == 4 || map[x][y - 1] == 5) que.push({ x,y - 1, t + 1 }); if (x + 1 >= 0 && x + 1 < N && visit[x + 1][y] == 0 && map[x + 1][y] == 1 || map[x + 1][y] == 2 || map[x + 1][y] == 4 || map[x + 1][y] == 7) que.push({ x + 1, y, t + 1 }); if (x - 1 >= 0 && x - 1 < N && visit[x - 1][y] == 0 && map[x - 1][y] == 1 || map[x - 1][y] == 2 || map[x - 1][y] == 5 || map[x - 1][y] == 6) que.push({ x - 1, y, t + 1 }); break; case 2: // 상 하 if (x + 1 >= 0 && x + 1 < N && visit[x + 1][y] == 0 && map[x + 1][y] == 1 || map[x + 1][y] == 2 || map[x + 1][y] == 4 || map[x + 1][y] == 7) que.push({ x + 1, y, t + 1 }); if (x - 1 >= 0 && x - 1 < N && visit[x - 1][y] == 0 && map[x - 1][y] == 1 || map[x - 1][y] == 2 || map[x - 1][y] == 5 || map[x - 1][y] == 6) que.push({ x - 1, y, t + 1 }); break; case 3: // 좌 우 if (y + 1 >= 0 && y + 1 < M && visit[x][y + 1] == 0 && map[x][y + 1] == 1 || map[x][y + 1] == 3 || map[x][y + 1] == 6 || map[x][y + 1] == 7) que.push({ x,y + 1, t + 1 }); if (y - 1 >= 0 && y - 1 < M && visit[x][y - 1] == 0 && map[x][y - 1] == 1 || map[x][y - 1] == 3 || map[x][y - 1] == 4 || map[x][y - 1] == 5) que.push({ x,y - 1, t + 1 }); break; case 4: // 상 우 if (x - 1 >= 0 && x - 1 < N && visit[x - 1][y] == 0 && map[x - 1][y] == 1 || map[x - 1][y] == 2 || map[x - 1][y] == 5 || map[x - 1][y] == 6) que.push({ x - 1, y, t + 1 }); if (y + 1 >= 0 && y + 1 < M && visit[x][y + 1] == 0 && map[x][y + 1] == 1 || map[x][y + 1] == 3 || map[x][y + 1] == 6 || map[x][y + 1] == 7) que.push({ x,y + 1, t + 1 }); break; case 5: // 하 우 if (y + 1 >= 0 && y + 1 < M && visit[x][y + 1] == 0 && map[x][y + 1] == 1 || map[x][y + 1] == 3 || map[x][y + 1] == 6 || map[x][y + 1] == 7) que.push({ x,y + 1, t + 1 }); if (x + 1 >= 0 && x + 1 < N && visit[x + 1][y] == 0 && map[x + 1][y] == 1 || map[x + 1][y] == 2 || map[x + 1][y] == 4 || map[x + 1][y] == 7) que.push({ x + 1, y, t + 1 }); break; case 6: // 하 좌 if (x + 1 >= 0 && x + 1 < N && visit[x + 1][y] == 0 && map[x + 1][y] == 1 || map[x + 1][y] == 2 || map[x + 1][y] == 4 || map[x + 1][y] == 7) que.push({ x + 1, y, t + 1 }); if (y - 1 >= 0 && y - 1 < M && visit[x][y - 1] == 0 && map[x][y - 1] == 1 || map[x][y - 1] == 3 || map[x][y - 1] == 4 || map[x][y - 1] == 5) que.push({ x,y - 1, t + 1 }); break; case 7: // 상 좌 if (x - 1 >= 0 && x - 1 < N && visit[x - 1][y] == 0 && map[x - 1][y] == 1 || map[x - 1][y] == 2 || map[x - 1][y] == 5 || map[x - 1][y] == 6) que.push({ x - 1, y, t + 1 }); if (y - 1 >= 0 && y - 1 < M && visit[x][y - 1] == 0 && map[x][y - 1] == 1 || map[x][y - 1] == 3 || map[x][y - 1] == 4 || map[x][y - 1] == 5) que.push({ x,y - 1, t + 1 }); break; default: break; } } ans = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (visit[i][j] == 1) { ans++; } } } int que_length = que.size(); for (int i = 0; i < que_length; i++) { que.pop(); } } int main() { int T; cin >> T; for (int tc = 1; tc <= T; tc++) { map_init(); visit_init(); problemIn(); solve(); cout << "#" << tc << " " << ans << endl; } } |