[백준 4991] 로봇 청소기

https://www.acmicpc.net/problem/4991

4991번: 로봇 청소기

#include <cstdio>
#include <cstring>
#include <queue>
int R, C;
char board[20 + 2][20 + 2];
int rx, ry;
int d_num;
int total;

struct _st
{
	int x, y;
	int move;
	int clean;
};
std::queue<_st> Q;
int visited[20 + 2][20 + 2][1 << 11];

void input()
{
	// init
	memset(board, '0', sizeof(board));
	memset(visited, 0, sizeof(visited));
	Q = {};
	total = 0;
	d_num = 0;

	for (int i = 0; i < R; i++) {
		scanf("%s", &board[i]);
		for (int j = 0; j < C; j++) {
			if (board[i][j] == 'o') {
				rx = i;
				ry = j;
				board[i][j] = '.';
			}	
			else if (board[i][j] == '*') {
				board[i][j] = d_num + '0';
				d_num++;
			}
		}
	}
	total = 1 << d_num;
}

int BFS()
{
	// dir
	int dir_x[4] = { 0, 0 ,1, -1 };
	int dir_y[4] = { 1, -1, 0, 0 };

	// init
	Q = {};
	memset(visited, 0, sizeof(visited));
	Q.push({ rx, ry, 0, 0 });
	visited[rx][ry][0] = 1;

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		if (data.clean == total - 1) return data.move;

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > R - 1 || ny < 0 || ny > C - 1) continue;
			if (board[nx][ny] == 'x') continue;
			if (visited[nx][ny][data.clean]) continue;

			if (board[nx][ny] >= '0' && board[nx][ny] <= '9') {
				int room = board[nx][ny] - '0';
				int nclean = data.clean | (1 << room);
				if (visited[nx][ny][nclean] == 0) {
					Q.push({ nx, ny, data.move + 1, nclean });
					visited[nx][ny][nclean] = 1;
					continue;
				}
			}
			Q.push({ nx, ny, data.move + 1, data.clean });
			visited[nx][ny][data.clean] = 1;
		} 
	}
	return -1;
}


int main()
{
	while (1) {
		scanf("%d %d", &C, &R);
		if (C == 0 && R == 0) return 0;
		input();
		printf("%d\n", BFS());
	}
	return 0;
}

rx, ry 갱신하면서 Flood-Fill로 풀면 틀린다. 

BFS로 출발지점 -> 도착지점 까지의 최단거리를 구할 수 는 있지만, "전체 이동 횟수의 최솟값"을 고려할 수 없기 때문이다.  

 

이 문제의 경우, 더러운 칸의 개수가 10개를 넘지 않으므로 비트마스킹을 쓸 수 있다.