SWEA 1953 : [모의 SW 역량테스트] 탈주범 검거

문제

---

문제 풀어보기

 

 

풀이

---

 

 

비트 마스크를 통해 길이 이어져있는지만 확인하면서

BFS를 하면 풀 수 있는 간단한 문제입니다.

 

 

그 간단한 문제를 저는 엄청 실수를 많이 했네요.

비트 마스크 할 때 항상 하는 실수인데

이진수랑 십진수를 자꾸 바꿔 쓰는 게 문제네요...

 

 

여러분들은 꼭 이진수 1000을 십진수 8이라고 쓰시기 바랍니다.

 

 

코드

---

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

using namespace std;
#define safe(x,y) x>=n || x<0 || y<0 || y>=m

int dx[] = { 1,-1 ,0,0 };
int dy[] = { 0,0,1,-1 };
// 아래 위 오른쪽 왼쪽
int pipe[] = { 0, 15, 12, 3, 6, 10 , 9, 5 };
int arr[55][55];
int d[55][55];
int n, m, r, c, l;

int bfs() {

	queue<pair<int, int>> q;
	memset(d, 0, sizeof(d));
	q.push({ r, c });
	d[r][c] = 1;
	int ans = 0;

	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int k = 0; k < 4; k++) {
			int nx = x + dx[k];
			int ny = y + dy[k];
			if (safe(nx, ny)) continue;
			if (arr[nx][ny] == 0) continue;
			if (d[nx][ny] >= 1) continue;
			int reverse;
			if (k % 2 == 0) reverse = k + 1;
			else reverse = k - 1;
			if ((arr[x][y] & (8 >> k)) && (arr[nx][ny] & (8 >>  reverse))) {
				q.push({nx, ny});
				d[nx][ny] = d[x][y] + 1;
			}

		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (d[i][j] >= 1 && d[i][j] <= l) ans++;
		}
	}

	return ans;
}



int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int T;

	cin >> T;
	for (int t = 1; t <= T; t++) {
		
		cin >> n >> m >> r >> c >> l;


		for (int i = 0; i < n; i++) {
			for (int j = 0, temp; j < m; j++) {
				cin >> temp;
				arr[i][j] = pipe[temp];
			}
		}

		int ans = bfs();
		cout << "#" << t << ' ';
		cout << ans << endl;

	}




	return 0;
}