[swea 1953] 탈주범 검거

분류 

구현

 

요구사항

탈주범이 제한시간 동안 이동할 수 있는 파이프 수 구하기

 

풀이

기본적으로 bfs로 구현한다

조건은 현재 -> 다음 파이프로 이동할때 가능한가 확인한다

가능 하다면 visit +1 을 해준다

 

#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
int n, m, r, c,l;
int map[55][55];
int visit[55][55];
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,-1,0,1 };
int ans = 0;
bool check(int dir,int next) {
	if (dir == 0) {
		if (next == 1 || next == 2 || next == 5 || next == 6)
			return true;
	}
	else if (dir == 1) {
		if (next == 1 || next == 3 || next == 4 || next == 5)
			return true;
	}
	else if (dir == 2) {
		if (next == 1 || next == 2 || next == 4 || next == 7)
			return true;
	}
	else if (dir == 3) {
		if (next == 1 || next == 3 || next == 6 || next == 7)
			return true;
	}
	return false;
}
void solve() {
	memset(visit, 0, sizeof(visit));
	queue<pair<int, int>> q;
	q.push({ r,c });
	visit[r][c] = 1;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		int now = map[x][y];
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nr = x + dr[i];
			int nc = y + dc[i];
			if (nr < 0 || nc < 0 || nr >= n || nc >= m) 
				continue;
			if (visit[nr][nc] == 0) {
				int next = map[nr][nc];
				if (now == 1) {
					if (check(i, map[nr][nc])) {
						visit[nr][nc] = visit[x][y]+1;
						q.push({ nr,nc });
					}
				}
				else if (now == 2) {
					if (i == 0 || i == 2) {
						if (check(i, next)) {
							visit[nr][nc] = visit[x][y] + 1;
							q.push({ nr,nc });
						}
					}
				}
				else if (now == 3) {
					if (i == 1 || i == 3) {
						if (check(i, next)) {
							visit[nr][nc] = visit[x][y] + 1;
							q.push({ nr,nc });
						}
					}
				}
				else if (now == 4) {
					if (i == 0 || i == 3) {
						if (check(i, next)) {
							visit[nr][nc] = visit[x][y] + 1;
							q.push({ nr,nc });
						}
					}
				}
				else if (now == 5) {
					if (i == 3 || i == 2) {
						if (check(i, next)) {
							visit[nr][nc] = visit[x][y] + 1;
							q.push({ nr,nc });
						}
					}
				}
				else if (now == 6) {
					if (i == 1 || i == 2) {
						if (check(i, next)) {
							visit[nr][nc] = visit[x][y] + 1;
							q.push({ nr,nc });
						}
					}
				}
				else if (now == 7) {
					if (i == 1 || i == 0) {
						if (check(i, next)) {
							visit[nr][nc] = visit[x][y] + 1;
							q.push({ nr,nc });
						}
					}
				}
			}

		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (visit[i][j]!=0 &&visit[i][j] <= l) {
				ans++;
			}
			//cout << visit[i][j] << " ";
		}
		//cout << endl;
	}
}
int main() {
	int t;
	scanf("%d", &t);
	for (int tc = 1; tc <= t; tc++) {
		ans = 0;
		scanf("%d%d%d%d%d", &n, &m, &r, &c, &l);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				scanf("%d", &map[i][j]);
			}
		}
		solve();
		printf("#%d %d\n", tc, ans);
	}

}