1953. 탈주범 검거

static int N, M, R, C, L;
static int board[50][50];
static bool visit[50][50];
static queue<pair<int, int>> q;
static int d[4][2] = {
	-1, 0, //up
	1, 0, //down
	0, -1, //left
	0, 1 //right
};
static int types[4][4] = {
	1, 2, 4, 7, //위로갈 수 있는 type
	1, 2, 5, 6, //아래로 갈 수 있는 type
	1, 3, 6, 7, //좌로 갈 수 있는 type
	1, 3, 4, 5 //우로 갈 수 있는 type
};
static int avail[4][4] = {
	1, 2, 5, 6, //위로 갈 때 필요한 type
	1, 2, 4, 7, //아래로 갈 때 필요한 type
	1, 3, 4, 5, //좌로 갈 때 필요한 type
	1, 3, 6, 7 //우로 갈 때 필요한 type
};

static bool out_of_bound(int y, int x)
{
	if (y < 0 || y >= N)
		return true;
	if (x < 0 || x >= M)
		return true;
	return false;
}

static bool check(int dir, int ny, int nx)
{
	int type = board[ny][nx];
	for (int i = 0; i < 4; i++)
	{
		//다음 type이 현재 방향에서 갈 수 있게 
		//연결된 type이라면
		if (type == avail[dir][i])
		{
			//방문하지 않았으면
			if (!visit[ny][nx])
			{
				visit[ny][nx] = true;
				q.push({ ny, nx });
				return true;
			}
		}
	}
	return false;
}

static int solution()
{
	int ret = 0;

	scanf("%d %d %d %d %d", &N, &M, &R, &C, &L);
	for (int y = 0; y < N; y++)
	{
		for (int x = 0; x < M; x++)
		{
			scanf("%d", &board[y][x]);
		}
	}

	memset(visit, false, sizeof(visit));
	q.push({ R, C });
	visit[R][C] = true;
	ret += 1;

	//0 -> 1 에서 맨홀 뚜겅을 통해 탈출한 것은 위에서 처리 하였으므로
	for (int t = 1; t < L; t++)
	{
		int sz = q.size(); //현재 큐에 있는 것에 대해서만
		for (int cnt = 0; cnt < sz; cnt++)
		{
			pair<int, int> cur = q.front();
			q.pop();

			int y = cur.first, x = cur.second;
			int type = board[y][x];

			//모든 방향으로
			for (int dir = 0; dir < 4; dir++)
			{
				for (int i = 0; i < 4; i++)
				{
					//현재 type이 해당 방향으로 갈 수 있는 type이라면,
					if (type == types[dir][i])
					{
						int ny = y + d[dir][0];
						int nx = x + d[dir][1];

						if (!out_of_bound(ny, nx))
						{
							if (check(dir, ny, nx))
								ret += 1;
						}
						break;
					}
				}		
			}
		}
	}

	while (q.size())
		q.pop();
	return ret;
}