ICPC 国内予選2006D カーリング 2.0 AOJ 1144

解法：深さ優先探索でゴリ押す
特に難しいところはない。計算量も気にしない。

#include <bits/stdc++.h>
#include <map>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
 
typedef long long ll;
typedef pair<double, int> P;
typedef tuple<int, int, int> T;
 
const ll MOD=1e9+7;
const ll INF=1e18;
 
int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};

int ans;
int w,h;
void solve(int n,int y,int x,int ban[22][22]){

    if(n > 10 || n >= ans) return;

    for(int k = 0;k < 4;k++){
        int ni = y + dy[k],nj = x + dx[k];
        if(ban[ni][nj] == -1 || ban[ni][nj] == 1)continue;
        if(ban[ni][nj] == 3){
            ans = min(ans,n);
            return;
        }
        while(true){
            ni += dy[k]; nj += dx[k];
            int state = ban[ni][nj];
            if(state == 3){
                ans = min(ans,n);
                return;
            }else if(state == 1){
                ban[ni][nj] = 0;
                solve(n+1,ni-dy[k],nj-dx[k],ban);
                ban[ni][nj] = 1;
                break;
            }else if(state == -1){
                break;
            }
        }
    }
}

int main(){
    int ban[22][22];
    
    while(1){
        cin >> w >> h;
        if(w + h == 0)break;
        ans = 11;
        int x,y;
        for(int i = 1;i <= h;i++){
            for(int j = 1;j <= w;j++){
                cin >> ban[i][j];
                if(ban[i][j] == 2){
                    y = i; x = j; ban[i][j] = 0;
                }
            }
        }
        for(int i = 0;i <= h+1;i++){
            ban[i][0] = -1;
            ban[i][w+1] = -1;
        }
        for(int j = 0;j <= w+1;j++){
            ban[0][j] = -1;
            ban[h+1][j] = -1;
        }
        solve(1,y,x,ban);
        if(ans == 11) ans = -1;
        cout << ans << endl;
    }
}