BOJ 14306 Monster Path (Small)

문제 링크입니다.

문제 요약

격자판마다 몬스터가 한 마리씩 있습니다. 상하좌우로 움직여 해당 칸에 방문할 때마다 그 몬스터 잡기를 시도할 수 있습니다. 몬스터를 잡을 확률은 그 칸에 몬스터 유인기가 있으면 $p$, 아니면 $q$입니다. 이미 몬스터를 잡은 칸에 다시 방문했다고 몬스터를 또 잡을 수는 없습니다.

최적의 방법으로 $S$번 이동했을 때 잡을 수 있는 몬스터의 수의 최대 기댓값을 구하세요.

다 해 보기

움직일 수 있는 방향은 상하좌우 4가지 뿐이고, $S$가 5 이하이므로 가능한 경로의 가짓수는 $2^{10} = 1024$ 이하입니다.

어떤 칸에 처음 방문했을 때 $r$의 확률로 몬스터를 잡을 수 있다고 합시다. 그뒤 그 칸에 다시 방문해 몬스터를 잡을 확률은, 저번 방문에서 몬스터를 잡지 못했어야 하므로 $(1-r)r$이 됩니다.

같은 논리로, 어떤 칸에 방문할 때마다 해당 칸에서 몬스터를 잡을 확률을 기댓값에 더한 뒤 해당 칸의 확률에 $(1-r)$을 곱하는 방식으로 진행하면 각 경로마다 ${\cal O}(S)$에 기댓값을 구할 수 있고, 마찬가지로 ${\cal O}(S)$에 각 칸에서 몬스터를 잡을 확률을 초기 상태로 롤백할 수 있습니다. 입력 제외 시간 복잡도는 테스트 케이스 당 ${\cal O}(S 2^S)$입니다.

Large도 같은 방법으로 해결할 수 있습니다. 경계를 벗어났다가 돌아오는 경로가 생기지 않도록 유의해 주세요.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
const int dy[]={-1,0,1,0},dx[]={0,1,0,-1};

char board[25][25];
ld d[25][25];

ld solve(){
	int n, m, sy, sx, t; cin >> n >> m >> sy >> sx >> t; sy++; sx++;
	ld p, q; cin >> p >> q;
	for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++){
		cin >> board[i][j];
		if(board[i][j] == 'A') d[i][j] = p;
		else d[i][j] = q;
	}
	ld ans = 0;
	for(int path = 0; path < (1<<(2*t)); path++){
		int y = sy, x = sx; ld tmp = 0; bool ok = 1;
		for(int i = 0; i < t; i++){
			int k = (path>>(i*2))&3;
			y += dy[k]; x += dx[k];
			if(y < 1 || y > n || x < 1 || x > m){
				ok = 0; continue;
			}
			tmp += d[y][x];
			if(board[y][x] == 'A') d[y][x] *= 1-p;
			else d[y][x] *= 1-q;
		}
		if(ok) ans = max(ans, tmp);
		y = sy; x = sx;
		for(int i = 0; i < t; i++){
			int k = (path>>(i*2))&3;
			y += dy[k]; x += dx[k];
			if(y < 1 || y > n || x < 1 || x > m) continue;
			if(board[y][x] == 'A') d[y][x] = p;
			else d[y][x] = q;
		}
	}
	return ans;
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	int T; cin >> T; cout << fixed << setprecision(12);
	for(int tc = 1; tc <= T; tc++) cout << "Case #" << tc << ": " << solve() << '\n';
}