JOI 春合宿 2012-day3 Sokoban
問題文 : 倉庫番
解法 :
「倉庫番の逆」を考える. すなわち, 目標地点から箱を引っ張りまわすBFS を考える. 箱の置き方がO(MN) 個, 隣接する頂点がたかだか4 個であるため, 状態数はO(MN) である.
各状態に遷移したら, 答えには連結成分の大きさを足してやれば良い. 連結成分の大きさは何回かのDFS で求まる.
ある頂点を取り除いた際の4 つの頂点の接続関係を用いれば, うまくこの足す作業を行うことができる.
コード :
#include <cstdio> #include <cstring> #include <queue> #include <algorithm> using namespace std; typedef long long lint; int M, N; int reachSize; int size[1024][1024][4]; int type[1024][1024][4]; char map[1024][1024]; bool vis[1024][1024]; bool done[1024][1024][4]; int dy[] = {0, 1, 0, -1}, dx[] = {1, 0, -1, 0}; struct Event { int ty, tx, dir; Event(int ty, int tx, int dir) : ty(ty), tx(tx), dir(dir) {} Event(){} }; bool valid(int ny, int nx) { return (0 <= ny && ny < M && 0 <= nx && nx < N && map[ny][nx] != '#'); } int rev(int dir) { if (dir >= 2) return (dir - 2); return (dir + 2); } int countReach(int sy, int sx) { int ret = 1; vis[sy][sx] = true; for (int i = 0; i < 4; i++){ int ny = sy + dy[i], nx = sx + dx[i]; if (valid(ny, nx) && !vis[ny][nx]){ ret += countReach(ny, nx); } } return (ret); } int fill(int my, int mx, int dir) { int ret = 1; vis[my][mx] = true; for (int i = 0; i < 4; i++){ int ny = my + dy[i], nx = mx + dx[i]; if (valid(ny, nx) && !vis[ny][nx]){ int c = fill(ny, nx, i); ret += c; size[my][mx][i] = c; } } if (~dir) size[my][mx][rev(dir)] = reachSize - ret; return (ret); } int t[1024][1024]; int ord[1024][1024], fin[1024][1024], low[1024][1024]; vector<pair<int, int> > chi[1024][1024]; void predfs(int sy, int sx, int py, int px, int &k) { vis[sy][sx] = true; ord[sy][sx] = low[sy][sx] = k++; for (int i = 0; i < 4; i++){ int ny = sy + dy[i], nx = sx + dx[i]; if (valid(ny, nx) && !vis[ny][nx]){ predfs(ny, nx, sy, sx, k); chi[sy][sx].push_back(make_pair(ny, nx)); low[sy][sx] = min(low[sy][sx], low[ny][nx]); } else if (valid(ny, nx) && !(ny == py && nx == px)){ low[sy][sx] = min(low[sy][sx], ord[ny][nx]); } } fin[sy][sx] = k++; } bool isDecendant(int uy, int ux, int vy, int vx) { return (ord[vy][vx] <= ord[uy][ux] && fin[uy][ux] <= fin[vy][vx]); } pair<int, int> getChild(int uy, int ux, int vy, int vx) { for (int i = 0; i < chi[uy][ux].size(); i++){ if (isDecendant(vy, vx, chi[uy][ux][i].first, chi[uy][ux][i].second)) return (chi[uy][ux][i]); } return (make_pair(-1, -1)); } bool isConnected(int ny, int nx, int ny2, int nx2, int vy, int vx) { if (!isDecendant(ny, nx, vy, vx) && !isDecendant(ny2, nx2, vy, vx)) return (true); else if (isDecendant(ny, nx, vy, vx) && isDecendant(ny2, nx2, vy, vx)){ pair<int, int> u1 = getChild(vy, vx, ny, nx), u2 = getChild(vy, vx, ny2, nx2); if (u1 == u2 || (low[u1.first][u1.second] < ord[vy][vx] && low[u2.first][u2.second] < ord[vy][vx])){ return (true); } } else { pair<int, int> u; if (isDecendant(ny, nx, vy, vx)) u = getChild(vy, vx, ny, nx); else u = getChild(vy, vx, ny2, nx2); if (low[u.first][u.second] < ord[vy][vx]) return (true); } return (false); } void dfs(int vy, int vx) { vis[vy][vx] = true; if (!valid(vy, vx)) return; for (int i = 0; i < 4; i++) type[vy][vx][i] = i; for (int i = 0; i < 4; i++){ int ny = vy + dy[i], nx = vx + dx[i]; for (int j = i + 1; j < 4; j++){ int ny2 = vy + dy[j], nx2 = vx + dx[j]; if (!valid(ny, nx) || !valid(ny2, nx2)) continue; if (isConnected(ny, nx, ny2, nx2, vy, vx)){ type[vy][vx][j] = min(type[vy][vx][j], type[vy][vx][i]); type[vy][vx][i] = min(type[vy][vx][j], type[vy][vx][i]); } } } for (int i = 0; i < 4; i++){ int ny = vy + dy[i], nx = vx + dx[i]; if (valid(ny, nx) && !vis[ny][nx]) dfs(ny, nx); } } int main() { scanf("%d %d", &M, &N); int sy, sx; for (int i = 0; i < M; i++){ scanf("%s", map[i]); for (int j = 0; j < N; j++){ if (map[i][j] == 'X'){ sy = i; sx = j; } } } memset(vis, 0, sizeof(vis)); reachSize = countReach(sy, sx) - 1; memset(vis, 0, sizeof(vis)); fill(sy, sx, -1); memset(vis, 0, sizeof(vis)); int k = 0; predfs(sy, sx, -1, -1, k); memset(vis, 0, sizeof(vis)); dfs(sy, sx); lint ans = 0; queue<Event> q; for (int i = 0; i < 4; i++){ done[sy][sx][i] = true; if (valid(sy + dy[i], sx + dx[i])){ q.push(Event(sy + dy[i], sx + dx[i], i)); } } for (; q.size(); q.pop()){ Event x = q.front(); if (done[x.ty][x.tx][type[x.ty][x.tx][x.dir]]) continue; int ny = x.ty + dy[x.dir], nx = x.tx + dx[x.dir]; if (valid(ny, nx)){ for (int i = 0; i < 4; i++){ if (type[x.ty][x.tx][i] == type[x.ty][x.tx][x.dir]){ ans += size[x.ty][x.tx][i]; t[x.ty][x.tx] += size[x.ty][x.tx][i]; } } for (int i = 0; i < 4; i++){ if (type[x.ty][x.tx][i] == type[x.ty][x.tx][x.dir]) if (valid(x.ty + dy[i], x.tx + dx[i])) q.push(Event(x.ty + dy[i], x.tx + dx[i], i)); } done[x.ty][x.tx][type[x.ty][x.tx][x.dir]] = true; } } printf("%lld\n", ans); return (0); }