AOJ 1144 Curling 2.0 Time Limit : 1 sec, Memory Limit : 65536 KB

AOJ_1144.cpp

#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <cmath>

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

using namespace std;

typedef vector< vector<int> > field;

int w, h;
field f, closed;
int mx[] = {0, 0, 1, -1},
    my[] = {1, -1, 0, 0};

int in_range(int x, int y, int w, int h) {
    return (int)(0 <= x && x < w && 0 <= y && y < h);
}

int bt(int x, int y, int step) {
    int res = INT_MAX, tmp;

    // 終了条件
    if ( step == 10 ) {
        return res;
    }

    // 上下左右に進めるなら進む
    REP(i, 4) {
        int nx = x, ny = y;

        while(1) {
            nx += mx[i];
            ny += my[i];

            if ( !in_range(nx, ny, w, h) ) {
                break;
            }

            if ( f[ny][nx] == 1 ) {
                break;
            } else if ( f[ny][nx] == 3 ) {
                return step + 1;
            }
        }

        if ( !in_range(nx, ny, w, h) || abs(x-nx) == 1 || abs(y-ny) == 1 ) continue;

        // 障害物を破壊
        f[ny][nx] = 0;
        tmp = bt(nx-mx[i], ny-my[i], step+1);
        f[ny][nx] = 1;

        // 最小手の更新
        if ( tmp < res )
            res = tmp;
    }

    return res;
}

int main() {
    int fx, fy, res;

    while( cin >> w >> h, w || h ) {
        f = field(h, vector<int>(w));

        // 入力
        REP(i, h) {
            REP(j, w) {
                cin >> f[i][j];
                if ( f[i][j] == 2 ) {
                    fx = j;
                    fy = i;
                }
            }
        }

        res = bt(fx, fy, 0);

        if ( res != INT_MAX )
            cout << res;
        else
            cout << -1;
        cout << endl;
    }

    return 0;
}