AOJ 0247 Ice Maze

問題文

Ice Maze

感想

本番じゃ手出したくない部類の問題だなあ。

枝刈り探索。semiexpが自明な枝刈りするだけで通ったと言っていたのを思い出して解いた。

ただ1.0sとか厳しくて、1.5sくらいでTLEしててハマってた。もっと自明な枝刈りしたら普通に通ってワロス。

解法

• まず氷をグループ分けする。
• 全探索をする。やり方は下に書く。
• 蛇を作らない(つまり足跡を付けながら移動するとすると、直前に居た位置以外の4近傍で隣接している部分に足跡があったら、それは短絡できるので探索打ち切って枝刈り。)
• 今得れている最短以上の手数確定したら枝刈り。
• 今いる位置からゴールまでのマンハッタン距離は少なくとも掛かるので、今のコストにそれ足したコストが最短コスト以上だったら枝刈り。

2番目までの枝刈りで1.5sくらい。3番目の枝刈りで0.2sくらいで通った。

ソース

#include <iostream>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i = 0 ; i < n ; i++)
 
char c[14][14];
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
 
int belong[14][14];
int ok[10000];
int gx,gy;
 
int ans = 0;
int ccc = 0;
int dfs(int x,int y,int C,int px,int py){
    if( c[y][x] == '#' || c[y][x] == '*') return 0;
    if( C + abs(x-gx) + abs(y-gy) >= ans ) return 0;
    if( c[y][x] == 'G'){
        ans = C;
        return 0;
    }
    for(int i = 0 ; i < 4 ; i++){
        int tx = x + dx[i];
        int ty = y + dy[i];
        if( px == tx && ty == py ) continue;
        if( c[ty][tx] == '*' ) return 0;
    }
    char cur = c[y][x];
    c[y][x] = '*';
    for(int i = 0 ; i < 4 ; i++){
        int tx = x + dx[i];
        int ty = y + dy[i];
        if( c[ty][tx] == 'X' ){
            int b = belong[ty][tx];
            if( ok[b] > 0 ){
                ok[b]--;
                dfs(tx,ty,C+1,x,y);
                ok[b]++;
            }
        }else{
            dfs(tx,ty,C+1,x,y);
        }
    }
    c[y][x] = cur;
    return 0;
}
int grouping(int x,int y,int k){
    if( c[y][x] != 'X') return 0;
    if( belong[y][x] != -1 ) return 0;
    belong[y][x] = k;
    ccc++;
    for(int i = 0 ; i < 4 ; i++)
        grouping(x+dx[i],y+dy[i],k);
}
 
int main(){
    ios_base::sync_with_stdio(false);
    int W,H;
    while(cin >> W >> H && W){
        rep(i,14)rep(j,14) belong[i][j] = -1;
        rep(i,14)rep(j,14) 
            c[i][j] = '#';
        int sx , sy;
        for(int i = 0 ; i < H ; i++){
            for(int j = 0 ; j < W ; j++){
                cin >> c[i+1][j+1];
                if(c[i+1][j+1] == 'S'){
                    c[i+1][j+1] = '.';
                    sx = j+1 , sy = i+1;
                }else if(c[i+1][j+1] == 'G' ){
                    gx = j+1 , gy = i+1;
                }
            }
        }
        int k = 0;
        for(int i = 1 ; i <= H ; i++){
            for(int j = 1 ; j <= W ; j++){
                if( c[i][j] == 'X' && belong[i][j] == -1){
                    ccc = 0;
                    grouping(j,i,k);
                    ok[k] = ccc / 2;
                    k++;
                }
            }
        }
        ans = 1e7;
        dfs(sx,sy,0,-1,-1);
        cout << ans << endl;
         
    }
}