読者です 読者をやめる 読者になる 読者になる

JOI春合宿 倉庫番(Sokoban)

グリッドグラフだ〜〜〜という気持ちになって頑張る.
コードだけ上げておきます O(MN)

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 0; i < (int)n; ++i)

const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};

int n, m, sx, sy, zen;
ll ret;
int deg[1000010];
int dt[1000010];
int g[1000010][4];
int tr[1000010][4];
char ban[1010][1010];
bool can[1010][1010];
bool vis[1000010];
bool inv[1010][1010][4];
int ord[1000010], out[1000010], low[1000010];
int sz[1000010];
int par[1000010];
int now;
bool adj[1000010][4][4];

inline void pre(int y, int x){
    can[y][x] = true;
    rep(i, 4){
	int ny = y + dy[i];
	int nx = x + dx[i];
	if(ny >= 0 && ny < m && nx >= 0 && nx < n && ban[ny][nx] != '#' && !can[ny][nx]) pre(ny, nx);
    }
}

void pro(int v, int p){
    low[v] = ord[v] = now++;
    sz[v] = 1;
    par[v] = p;
    vis[v] = true;
    rep(i, deg[v]) if(g[v][i] != p){
	if(!vis[g[v][i]]){
	    tr[v][dt[v]++] = g[v][i];
	    pro(g[v][i], v);
	    sz[v] += sz[g[v][i]];
	    low[v] = min(low[v], low[g[v][i]]);
	}else{
	    low[v] = min(low[v], ord[g[v][i]]);
	}
    }
    out[v] = now++;
}

inline bool dec(int p, int q){ // p : ancestor of q
    return ord[p] <= ord[q] && out[q] <= out[p];
}

void set(int v){ //remove v
    int ap[4] = {-1};
    rep(i, deg[v]){
	int a = g[v][i];	
	if(dec(v, a)){
	    rep(j, dt[v]){
		if(dec(tr[v][j], a)){
		    ap[i] = tr[v][j];
		    break;
		}
	    }
	}
    }

    rep(i, deg[v]){
	int a = g[v][i];
	rep(j, deg[v]) if(i != j){
	    int b = g[v][j];
	    if(!(dec(v, a) || dec(v, b))) adj[v][i][j] = adj[v][j][i] = true;
	    else if(dec(v, a) && !dec(v, b)){
		adj[v][i][j] = adj[v][j][i] = (low[ap[i]] < ord[v]);
	    }else if(dec(v, a) && dec(v, b)){
		if(ap[i] == ap[j] || (low[ap[i]] < ord[v] && low[ap[j]] < ord[v])){
		    adj[v][i][j] = adj[v][j][i] = true;
		}
	    }
	}
    }
}

void calc(int y, int x, int dir){
    if(inv[y][x][dir]) return ;
    //printf("y : %d, x : %d, dir : %d\n", y, x, dir);
    inv[y][x][dir] = true;
    int v = y * n + x;
    if(!can[y][x]) set(v);
    can[y][x] = true;
    int px = x + dx[dir], py = y + dy[dir];
    int nv = py * n + px;
    int whi = -1;
    rep(i, deg[v]){
	if(g[v][i] == nv){
	    whi = i;
	    break;
	}
    }

    int kou[4];
    int piv = 0;
    //printf("whi : %d\n", whi);
    ll mi = 0;
    bool f = false;
    //printf("y : %d, x : %d, py : %d, px : %d\n", y, x, py, px);
    rep(i, deg[v]) {
	if((i == whi) || adj[v][whi][i]){
	    int dev = g[v][i];
	    if(dec(g[v][i], v)) f = true;
	    //printf("(%d %d) ", dev / n, dev % n);
	    kou[piv++] = g[v][i];
	}
    }
    //puts("");

    ll tmp = 0;
    if(par[v] != -1){
	rep(i, piv){
	    if(par[v] == kou[i]){
		tmp += zen - sz[v] - 1;
	    }
	}
    }

    rep(i, dt[v]){
	rep(j, piv){
	    if(tr[v][i] == kou[j]) tmp += sz[tr[v][i]];
	}
    }
    
    if(y != sy || x != sx) ret += tmp;
    //printf("y : %d, x : %d, dir : %d, add : %lld\n", y, x, dir, tmp);

    int d[4] = {-1};

    rep(i, piv){
	int ny = kou[i] / n, nx = kou[i] % n;
	int ndir = -1;
	int dify = ny - y, difx = nx - x;
	if(difx == 1 && dify == 0) ndir = 0;
	else if(difx == -1 && dify == 0) ndir = 1;
	else if(difx == 0 && dify == 1) ndir = 2;
	else ndir = 3;
	inv[y][x][ndir] = true;
	d[i] = ndir;
    }

    rep(i, piv){
	int ny = kou[i] / n, nx = kou[i] % n;
	py = ny + dy[d[i]];
	px = nx + dx[d[i]];
	if(px < 0 || py < 0 || px >= n || py >= m || ban[py][px] == '#') continue;
	//printf("(py, px) : (%d, %d), (ny, nx) : (%d, %d), ndir : %d\n", py, px, ny, nx, ndir);
	calc(ny, nx, d[i]);
    }
}

int main(){
    scanf("%d %d", &m, &n);
    rep(i, m){
	scanf("%s", ban[i]);
	rep(j, n) if(ban[i][j] == 'X'){
	    sy = i;
	    sx = j;
	    ban[i][j] = '.';
	}
    }
    pre(sy, sx);
    rep(i, m) rep(j, n) if(!can[i][j]) ban[i][j] = '#';
    memset(can, 0, sizeof(can));
    rep(i, m) rep(j, n){
	int y = i, x = j, v = i * n + j;
	if(ban[i][j] == '#') continue;
	rep(k, 4){
	    int ny = y + dy[k], nx = x + dx[k], nv = ny * n + nx;
	    if(ny >= 0 && ny < m && nx >= 0 && nx < n && ban[ny][nx] != '#'){
		g[v][deg[v]++] = nv;
	    }
	}
    }
    pro(n * sy + sx, -1);
    zen = sz[n * sy + sx];
    rep(i, 4){
	int nx = sx + dx[i], ny = sy + dy[i];
	if(nx < 0 || ny < 0 || nx >= n || ny >= m || ban[ny][nx] == '#') continue;
	int px = nx + dx[i], py = ny + dy[i];
	if(px < 0 || py < 0 || px >= n || py >= m || ban[py][px] == '#') continue;
	calc(ny, nx, i);
    }
    printf("%lld\n", ret);
    return 0;
}