[백준 16973] 직사각형 탈출

문제

www.acmicpc.net/problem/16973

16973번: 직사각형 탈출

 

풀이

1. 간단하게 생각해본다면 시작 점에서부터 BFS를 돌려 "왼쪽 위 점에서부터 오른쪽 아래 점까지 1이 포함되어 있는가?"를 확인하며 진행하면 될 것 같지만 $O(n*m*h*w)$로 시간 초과가 납니다.

 

2. "해당 점에서 부터 오른쪽 아래 점까지 1이 포함되어 있는가?"를 연산하며 중복된 칸을 계속 탐색하므로 이를 막기 위해 dp를 사용합니다. 이때 상태 정의는 "dp[i][j] = (0, 0)부터 (i, j)칸 까지 1의 개수의 합(누적합)"이며 첫 행과 첫 열을 누적해놓은 상태에서 상태 전이는 일반적인 2차원 누적합과 같습니다. $$ dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][ j - 1] + g[i - 1][j - 1] $$

 

3.  이제 "왼쪽 위 점에서 부터 오른쪽 아래 점까지 1이 포함되어 있는가?"는 왼쪽 위 점을 (a, b), 오른쪽 아래 점을 (c, d)라 할 때 아래와 같이 1의 개수를 $O(1)$에 구할 수 있습니다. 

 

 

코드

#include <bits/stdc++.h>
using namespace std;

const int dir[4][2] = { { -1,0 },{ 1,0 },{ 0,-1 },{ 0,1 } };
int n, m, h, w, g[1001][1001], dp[1001][1001], sr, sc, dr, dc;
bool vis[1001][1001];

int go(int r, int c) {
	if (r < 0 || c < 0) return 0;
	int& ret = dp[r][c];
	if (ret != -1) return ret;
	return ret = go(r - 1, c) + go(r, c - 1) - go(r - 1, c - 1) + g[r][c];
}

void bfs() {
	int cr, cc, nr, nc, cost, cnt, a, b, c, d;
	queue<tuple<int, int, int>> q;
	vis[sr][sc] = 1;
	q.push({ sr,sc,0 });
	while (!q.empty()) {
		tie(cr, cc, cost) = q.front(); q.pop();
		if (cr == dr && cc == dc) {
			cout << cost;
			return;
		}
		for (int i = 0; i < 4; i++) {
			nr = cr + dir[i][0], nc = cc + dir[i][1];
			if (nr < 0 || nr >= n || nc < 0 || nc >= m || vis[nr][nc] || g[nr][nc] || nr + h - 1 >= n || nc + w - 1 >= m) continue;
			a = nr, b = nc, c = nr + h - 1, d = nc + w - 1;
			cnt = go(c, d) - go(a - 1, d) - go(c, b - 1) + go(a - 1, b - 1);
			if (cnt) continue;
			vis[nr][nc] = 1;
			q.push({ nr,nc,cost + 1 });
		}
	}
	cout << -1;
}

int main() {
	cin.tie(NULL); cout.tie(NULL);
	ios_base::sync_with_stdio(false);
	memset(dp, -1, sizeof(dp));

	cin >> n >> m;
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < m; j++) 
			cin >> g[i][j];
	dp[0][0] = g[0][0];
	for (int i = 1; i < n; i++) dp[i][0] = dp[i - 1][0] + g[i][0];
	for (int i = 1; i < m; i++) dp[0][i] = dp[0][i - 1] + g[0][i];
	cin >> h >> w >> sr >> sc >> dr >> dc;
	sr--, sc--, dr--, dc--;
	bfs();
}