본문 바로가기
백준 알고리즘/구현

탈주범 검거 C++

by paysmile 2022. 4. 28.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;
const int MAX = 51;
int map[MAX][MAX];
int n, m;
int r, c, l;
int visited[MAX][MAX][4];
struct MOVE { int x, y; };
MOVE mv[4] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
//상 하 좌 우

bool CheckCango(int ii, int jj, int k) {
	if (map[ii][jj] == 1) {
		return true;
	}
	else if (map[ii][jj] == 2) {
		if (k == 0 || k == 1) return true;
		else return false;
	}
	else if (map[ii][jj] == 3) {
		if (k == 2 || k == 3) return true;
		else return false;
	}
	else if (map[ii][jj] == 4) {
		if (k == 1 || k == 2) return true;
		else return false;
	}
	else if (map[ii][jj] == 5) {
		if (k == 2 || k == 0) return true;
		else return false;
	}
	else if (map[ii][jj] == 6) {
		if (k == 3 || k == 0) return true;
		else return false;
	}
	else if (map[ii][jj] == 7) {
		if (k == 3 || k == 1) return true;
		else return false;
	}
}

int main(void) {
	int testcase;
	cin >> testcase;
	int index = 1;

	for (; testcase > 0; testcase--) {
		int answer = 0;
		cin >> n >> m;
		cin >> r >> c >> l;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				cin >> map[i][j];
			}
		}

		memset(visited, -1, sizeof(visited));
		queue<pair<pair<int, int>,int>> q;
		int time = 1;
		if (map[r][c] == 1) {
			q.push({ {r,c},0 });
			q.push({ { r,c },1});
			q.push({ { r,c },2 });
			q.push({ { r,c },3 });
			visited[r][c][0] = 1;
			visited[r][c][1] = 1;
			visited[r][c][2] = 1;
			visited[r][c][3] = 1;
		}
		else if (map[r][c] == 2) {
			q.push({ { r,c },0 });
			q.push({ { r,c },1 });
			visited[r][c][0] = 1;
			visited[r][c][1] = 1;
		}
		else if (map[r][c] == 3) {
			q.push({ { r,c },2 });
			q.push({ { r,c },3 });
			visited[r][c][2] = 1;
			visited[r][c][3] = 1;
		}
		else if (map[r][c] == 4) {
			q.push({ { r,c },0 });
			q.push({ { r,c },3 });
			visited[r][c][0] = 1;
			visited[r][c][3] = 1;
		}
		else if (map[r][c] == 5) {
			q.push({ { r,c },1 });
			q.push({ { r,c },3 });
			visited[r][c][1] = 1;
			visited[r][c][3] = 1;
		}
		else if (map[r][c] == 6) {
			q.push({ { r,c },1 });
			q.push({ { r,c },2 });
			visited[r][c][1] = 1;
			visited[r][c][2] = 1;
		}
		else if (map[r][c] == 7) {
			q.push({ { r,c },0 });
			q.push({ { r,c },2 });
			visited[r][c][0] = 1;
			visited[r][c][2] = 1;
		}

		while (!q.empty()) {
			if (time == l) break;
			int s = q.size();

			for (; s > 0; s--) {
				int ii = q.front().first.first;
				int jj = q.front().first.second;
				int d = q.front().second;
				q.pop();

				if (map[ii][jj] == 0) {
					continue;
				}
				else if (map[ii][jj] == 1) {
					for (int k = 0; k < 4; k++) {
						int movei = ii + mv[k].x;
						int movej = jj + mv[k].y;

						if (!(movei >= 0 && movei < n && movej >= 0 && movej < m)) continue;
						if (visited[movei][movej][k] == 1) continue;
						if (map[movei][movej] == 0) continue;
						if (CheckCango(movei, movej, k) == false) continue;

						visited[movei][movej][k] = 1;
						q.push({ {movei,movej},k });
					}
				}
				else if (map[ii][jj] == 2) {
					if (d == 0) {
						int movei = ii + mv[0].x;
						int movej = jj + mv[0].y;

						if (!(movei >= 0 && movei < n && movej >= 0 && movej < m)) continue;
						if (visited[movei][movej][0] == 1) continue;
						if (map[movei][movej] == 0) continue;
						if (CheckCango(movei, movej, 0) == false) continue;

						visited[movei][movej][0] = 1;
						q.push({ { movei,movej },0 });
					}
					else if (d == 1) {
						int movei = ii + mv[1].x;
						int movej = jj + mv[1].y;

						if (!(movei >= 0 && movei < n && movej >= 0 && movej < m)) continue;
						if (visited[movei][movej][1] == 1) continue;
						if (map[movei][movej] == 0) continue;
						if (CheckCango(movei, movej, 1) == false) continue;

						visited[movei][movej][1] = 1;
						q.push({ { movei,movej },1 });
					}
				}
				else if (map[ii][jj] == 3) {
					if (d == 2) {
						int movei = ii + mv[2].x;
						int movej = jj + mv[2].y;

						if (!(movei >= 0 && movei < n && movej >= 0 && movej < m)) continue;
						if (visited[movei][movej][2] == 1) continue;
						if (map[movei][movej] == 0) continue;
						if (CheckCango(movei, movej, 2) == false) continue;

						visited[movei][movej][2] = 1;
						q.push({ { movei,movej },2 });
					}
					else if (d == 3) {
						int movei = ii + mv[3].x;
						int movej = jj + mv[3].y;

						if (!(movei >= 0 && movei < n && movej >= 0 && movej < m)) continue;
						if (visited[movei][movej][3] == 1) continue;
						if (map[movei][movej] == 0) continue;
						if (CheckCango(movei, movej, 3) == false) continue;

						visited[movei][movej][3] = 1;
						q.push({ { movei,movej },3 });
					}
				}
				else if (map[ii][jj] == 4) {
					if (d == 1) {
						int movei = ii + mv[3].x;
						int movej = jj + mv[3].y;

						if (!(movei >= 0 && movei < n && movej >= 0 && movej < m)) continue;
						if (visited[movei][movej][3] == 1) continue;
						if (map[movei][movej] == 0) continue;
						if (CheckCango(movei, movej, 3) == false) continue;

						visited[movei][movej][3] = 1;
						q.push({ { movei,movej },3 });
					}
					else if (d == 2) {
						int movei = ii + mv[0].x;
						int movej = jj + mv[0].y;

						if (!(movei >= 0 && movei < n && movej >= 0 && movej < m)) continue;
						if (visited[movei][movej][0] == 1) continue;
						if (map[movei][movej] == 0) continue;
						if (CheckCango(movei, movej, 0) == false) continue;

						visited[movei][movej][0] = 1;
						q.push({ { movei,movej },0 });
					}
				}
				else if (map[ii][jj] == 5) {
					if (d == 2) {
						int movei = ii + mv[1].x;
						int movej = jj + mv[1].y;

						if (!(movei >= 0 && movei < n && movej >= 0 && movej < m)) continue;
						if (visited[movei][movej][1] == 1) continue;
						if (map[movei][movej] == 0) continue;
						if (CheckCango(movei, movej, 1) == false) continue;

						visited[movei][movej][1] = 1;
						q.push({ { movei,movej },1 });
					}
					else if (d == 0) {
						int movei = ii + mv[3].x;
						int movej = jj + mv[3].y;

						if (!(movei >= 0 && movei < n && movej >= 0 && movej < m)) continue;
						if (visited[movei][movej][3] == 1) continue;
						if (map[movei][movej] == 0) continue;
						if (CheckCango(movei, movej, 3) == false) continue;

						visited[movei][movej][3] = 1;
						q.push({ { movei,movej },3 });
					}
				}
				else if (map[ii][jj] == 6) {
					if (d == 3) {
						int movei = ii + mv[1].x;
						int movej = jj + mv[1].y;

						if (!(movei >= 0 && movei < n && movej >= 0 && movej < m)) continue;
						if (visited[movei][movej][1] == 1) continue;
						if (map[movei][movej] == 0) continue;
						if (CheckCango(movei, movej, 1) == false) continue;

						visited[movei][movej][1] = 1;
						q.push({ { movei,movej },1 });
					}
					else if (d == 0) {
						int movei = ii + mv[2].x;
						int movej = jj + mv[2].y;

						if (!(movei >= 0 && movei < n && movej >= 0 && movej < m)) continue;
						if (visited[movei][movej][2] == 1) continue;
						if (map[movei][movej] == 0) continue;
						if (CheckCango(movei, movej, 2) == false) continue;

						visited[movei][movej][2] = 1;
						q.push({ { movei,movej },2 });
					}
				}
				else if (map[ii][jj] == 7) {
					if (d == 1) {
						int movei = ii + mv[2].x;
						int movej = jj + mv[2].y;

						if (!(movei >= 0 && movei < n && movej >= 0 && movej < m)) continue;
						if (visited[movei][movej][2] == 1) continue;
						if (map[movei][movej] == 0) continue;
						if (CheckCango(movei, movej, 2) == false) continue;

						visited[movei][movej][2] = 1;
						q.push({ { movei,movej },2 });
					}
					else if (d == 3) {
						int movei = ii + mv[0].x;
						int movej = jj + mv[0].y;

						if (!(movei >= 0 && movei < n && movej >= 0 && movej < m)) continue;
						if (visited[movei][movej][0] == 1) continue;
						if (map[movei][movej] == 0) continue;
						if (CheckCango(movei, movej, 0) == false) continue;

						visited[movei][movej][0] = 1;
						q.push({ { movei,movej },0 });
					}
				}

			}
			time++;
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				bool flag = false;
				for (int k = 0; k < 4; k++) {
					if (visited[i][j][k] == 1) {
						flag = true;
						break;
					}
				}
				if (flag == true) answer++;
			}
		}

		cout << "#" << index << " " << answer << endl;
		index++;
	}
}
저작자표시 비영리 변경금지

'백준 알고리즘 > 구현' 카테고리의 다른 글

원자 소멸 시뮬레이션 C++  (0) 2022.04.29
등산로 조성 C++  (0) 2022.04.29
점심 식사시간 C++  (0) 2022.04.25
미생물 격리 C++  (0) 2022.04.25
무선 충전 C++  (0) 2022.04.25

관련글

티스토리툴바