Problem 1214 : Walking Ant

Problem G: Walking Ant
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1214

• 問題概要

アリが６回しかうごけない。でも、お菓子にいくと回復する。最短で何回うごけば巣にもどれるか。
もどれないときは-1をだせ。

• 解法

BFS。
今回はクラスにメゾットをいっぱい持たせてみた。
あんまり僕はこういう書き方しないから新鮮だった。
かきやすかったのでこれからこんなふうに書こう。

• ソース

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<sstream>
#include<cassert>
#include<queue>
#include<stack>

#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define pb         push_back
#define mp         make_pair
#define vint       vector<int>
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)
#define lli	    long long int
#define ld	    long double

#define N 8
#define HP 7

using namespace std;

int sx, sy, tx[] = {0, 1, 0, -1}, ty[] = {-1, 0, 1, -0}, h, w, m[N][N];
bool visited[N][N][HP];

void reset(){
  rep(i, N)rep(j, N){
    m[i][j] = 1;
    rep(k, HP){
      visited[i][j][k] = false;
    }
  }
}

class State{
public:
  int x, y, hp, cost;
  State(){
    hp = 6;
    x = sx;
    y = sy;
    cost = 0;
  }
  bool move(int now){
    int nx = x + tx[now], ny = y + ty[now];
    if(nx < 0 || ny < 0 || nx >= w || ny >= h){
      return false;
    }
    if( m[ny][nx] == 0){
      return false;
    }
    x = nx;
    y = ny;
    hp--;
    if(hp == 0)return false;
    if(m[ny][nx] == 4){
      hp = 6;
    }
    if(visited[ny][nx][hp])return false;
    visited[ny][nx][hp] = true;
    cost++;
    return true;
  }
  bool goal(){
    if(m[y][x] == 3)return true;
    return false;
  }
};

main(){
  while(cin >> w >> h){
    if(w+h == 0)break;
    reset();
    rep(i, h){
      rep(j, w){
	cin >> m[i][j];
	if(m[i][j] == 2){
	  sx = j;
	  sy = i;
	}	
      }
    }
    queue<State> Q;
    Q.push(State());
    bool flag = false;
    while(!Q.empty()){
      State s = Q.front();
      Q.pop();
      rep(i, 4){
	State now = s;
	if(now.move(i)){
	  if(now.goal()){
	    flag = true;
	    cout << now.cost << endl;
	    break;
	  }
	  Q.push(now);
	}
      }
      if(flag)break;
    }
    if(!flag)cout << -1 << endl;
  }
}