AOJ 0247 - Ice Maze

問題文 : AOJ 0247

解法 :

• 基本的には深さ優先探索を行う.


• ただし, それだけでは時間制限に間に合わないので, 反復深化深さ優先探索(IDDFS)を行う.


• 具体的には, 下界uを決めて, uよりコストがかかることがわかればuを増やすという事を行う. 下界から決めているので, はじめてゴールに到達できた時が最適解である.


• それ以外にも, マンハッタン距離を使った枝刈り(ソース参照)などを行うと高速でプログラムが動作する.

コード :

#include <cstdio>
#include <cmath>
#include <cstring>
  
using namespace std;
  
 
int W, H;
  
char map[16][16];
char g[16][16];
bool v[16][16];
  
int maxIce[128];
int ice[128];
  
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
 
int ans;
int px, py;
int sx, sy, gx, gy;
  
bool getMin(int ty, int tx, int turn)
{
      
    if (turn + abs(ty - gy) + abs(tx - gx) >= ans){
        return (false);
    }
      
    if (ty == gy && tx == gx){
        ans = turn;
        return (true);
    }
      
    for (int i = 0; i < 4; i++){
        int mx = tx + dx[i], my = ty + dy[i];
        if (0 <= mx && mx < W && 0 <= my && my < H && px != mx && py != my && v[my][mx]){
            return (false);
        }
    }
      
    for (int i = 0; i < 4; i++){
        int mx = tx + dx[i], my = ty + dy[i];
        px = tx, py = ty;
        if (0 <= mx && mx < W && 0 <= my && my < H && map[my][mx] != '#' && !v[my][mx]){
            if (g[my][mx] == -1){
                v[my][mx] = true;
                if (getMin(my, mx, turn + 1)) return (true);
                v[my][mx] = false;
            }
            else if (maxIce[g[my][mx]] >= ice[g[my][mx]] + 1){
                ice[g[my][mx]]++;
                v[my][mx] = true;
                if (getMin(my, mx, turn + 1)) return (true);
                v[my][mx] = false;
                ice[g[my][mx]]--;
            }
        }
    }
     
    return (false);
}
  
void label(int ty, int tx, int p)
{
    g[ty][tx] = p;
    maxIce[p]++;
      
    for (int i = 0; i < 4; i++){
        int mx = tx + dx[i], my = ty + dy[i];
          
        if (0 <= mx && mx < W && 0 <= my && my < H &&
                    map[my][mx] == 'X' && g[my][mx] == -1){
            label(my, mx, p);
        }
    }
}
  
int main()
{
    int idx;
      
    while (1){
        scanf("%d %d", &W, &H);
          
        if (W + H == 0){
            break;
        }
          
        for (int i = 0; i < H; i++){
            scanf("%s", map[i]);
            for (int j = 0; j < W; j++){
                if (map[i][j] == 'S'){
                    map[i][j] = '.';
                    sx = j, sy = i;
                }
                if (map[i][j] == 'G'){
                    map[i][j] = '.';
                    gx = j, gy = i;
                }
            }
        }
          
        memset(g, -1, sizeof(g));
        memset(maxIce, 0, sizeof(maxIce));
          
        idx = 0;
        for (int i = 0; i < H; i++){
            for (int j = 0; j < W; j++){
                if (map[i][j] == 'X' && g[i][j] == -1){
                    label(i, j, idx);
                    maxIce[idx++] /= 2;
                }
            }
        }
          
        memset(ice, 0, sizeof(ice));
        memset(v, 0, sizeof(v));
        px = py = -1;
        v[sy][sx] = true;
         
        ans = 0;
        while (!getMin(sy, sx, 0)){
            memset(ice, 0, sizeof(ice));
            memset(v, 0, sizeof(v));
            px = py = -1;
            v[sy][sx] = true;
            ans++;
        }
         
        printf("%d\n", ans);
    }
      
    return (0);
}