Sokoban

gistfile1.cpp

#include <cstdio>
#include <set>
using namespace std;
#define MP make_pair
typedef pair<int,int> P;
typedef pair<P,P> PP;
typedef long long ll;

int vx[]={1,0,-1,0},vy[]={0,1,0,-1};
char ban[1005][1005];
set<PP> kumi;
int M,N;
bool check(int x,int y){
    if(0<=x&&x<M&&0<=y&&y<N&&ban[x][y]!='#') return true;
    else return false;
}
int sx,sy;
void dfs(int px,int py,int hx,int hy){
    int movev,exisv;
    bool isrin=false;
    for(int v=0;v<4;v++){
        if(px+vx[v]==hx&&py+vy[v]==hy){
            isrin=true;
            exisv=v;
            movev=(v+2)%4;
        }
    }
    if(isrin){
        int pmx=px+vx[movev],pmy=py+vy[movev];
        if(check(pmx,pmy)){
            int hmx=hx+vx[movev],hmy=hy+vy[movev];
            if(!(hmx==sx&&hmy==sy)){
                PP now=MP(MP(pmx,pmy),MP(hmx,hmy));
                if(kumi.find(now)==kumi.end()){
                    kumi.insert(MP(MP(pmx,pmy),MP(hmx,hmy)));
                    dfs(pmx,pmy,hmx,hmy);
                }
            }
        }
    }
    for(int v=0;v<4;v++){
        if(isrin&&v==exisv) continue;
        int pmx=px+vx[v],pmy=py+vy[v];
        PP now=MP(MP(pmx,pmy),MP(hx,hy));
        if(!(hx==sx&&hy==sy)){
            if(check(pmx,pmy)&&kumi.find(now)==kumi.end()){
                kumi.insert(MP(MP(pmx,pmy),MP(hx,hy)));
                dfs(pmx,pmy,hx,hy);
            }
        }
    }
}
int main(){
    scanf("%d %d\n",&M,&N);
    for(int i=0;i<M;i++){
        scanf("%s\n",ban[i]);
    }
    for(int i=0;i<M;i++){
        for(int j=0;j<N;j++){
            if(ban[i][j]=='X'){
                sx=i;
                sy=j;
            }
        }
    }
    for(int v=0;v<4;v++){
        int nx1=sx+vx[v],ny1=sy+vy[v],nx2=nx1+vx[v],ny2=ny1+vy[v];
        if(check(nx1,ny1)&&check(nx2,ny2)){
            kumi.insert(MP(MP(nx2,ny2),MP(nx1,ny1)));
            dfs(nx2,ny2,nx1,ny1);
        }
    }
    ll ret=0;
    P st=MP(sx,sy);
    for(set<PP>::iterator it=kumi.begin();it!=kumi.end();it++){
        if(it->first!=st&&it->second!=st) ret++;
    }
    printf("%lld\n",ret);
}