ICPC 国内予選2010B 迷図と命ず AOJ 1166

解法：幅優先探索やるだけ。

#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<int, 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[35][35];
int wall[70][70];
int w,h;

bool check(int y1,int x1,int y2,int x2){
    if(min(min(x1,y1),min(x2,y2)) < 0 || max(x1,x2) >= w || max(y1,y2) >= h) return false;
    if(y1 == y2){
        if(wall[y1*2][min(x1,x2)] == 1){
            return false;
        }else{
            return true;
        }
    }else{
        if(wall[min(y1,y2)*2+1][x1] == 1){
            return false;
        }else{
            return true;
        }
    }
}

int main(){
    
    while(true){
        cin >> w >> h;
        if(w + h == 0) break;
        for(int i = 0;i < h;i++){
            for(int j = 0;j < w;j++){
                ans[i][j] = -1;
            }
        }
        for(int i = 0;i < 2*h-1;i++){
            for(int j = 0;j < w - 1 + i%2;j++){
                cin >> wall[i][j];
            }
        }
        ans[0][0] = 1;
        queue<P> que;
        que.push(P(0,0));
        int flag = 0;
        while(!que.empty()){
            P q = que.front(); que.pop();
            if(q.fs == h-1 && q.sc == w-1){
                flag = 1;
                cout << ans[q.fs][q.sc] << endl;
                break;
            }
            for(int i = 0;i < 4;i++){
                if( check(q.fs,q.sc,q.fs+dy[i],q.sc+dx[i]) == true && ans[q.fs+dy[i]][q.sc+dx[i]]==-1){
                    ans[q.fs+dy[i]][q.sc+dx[i]] = ans[q.fs][q.sc] + 1;
                    que.push(P(q.fs+dy[i],q.sc+dx[i]));
                }
            }
            
        }
        if(flag == 0){
            cout << 0 << endl;
        }
    }
}