Problem 1218 : Push!!

Problem C: Push!!
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1218

• 問題概要

ポケモンのチャンピョンロードのかいりきで石落とすやつ

みたいな感じ。

• 解法

BFS。
ただし、人が動けるところをDFSして求めながらする必要がある。

• ソース

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

#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 7

using namespace std;
int t[N][N];
bool can[N][N];
int dx[] = {0, 1, 0, -1}, dy[] = {-1, 0, 1, 0};
int w, h;
void reset(){
  rep(i, N)rep(j, N)can[i][j] = false;
}

void dfs(int x, int y, int cx, int cy){
  can[y][x] = true;
  rep(i, 4){
    int nx = x + dx[i], ny = y + dy[i];
    if(ny < 0 || nx < 0 || ny >= h || nx >= w)continue;
    if(can[ny][nx] || t[ny][nx] == 1)continue;
    if(cx == nx && cy == ny)continue;
    dfs(nx, ny, cx, cy);
  }
} 

class State{
public:
  int x, y, px, py, cnt;
  State(){
    cnt = 0;
  }
};

main(){
  while(cin >> w >> h){
    if(w + h == 0)break;
    State s;
    rep(i, h){
      rep(j, w){
	int tmp;
	cin >> tmp;
	if(tmp == 1 || tmp == 3){
	  t[i][j] = tmp;
	  continue;
	}
	if(tmp == 2){
	  s.x = j;
	  s.y = i;
	}
	if(tmp == 4){
	  s.py = i;
	  s.px = j;
	}
	t[i][j] = 0;
      }
    }

    bool visited[h][w][h][w];
    rep(i, h)rep(j, w)rep(k, h)rep(l, w)visited[i][j][k][l] = false;
    
    queue<State> Q;
    Q.push(s);
    bool flag = true;
    while(!Q.empty()){
      s = Q.front();
      Q.pop();
      if(t[s.y][s.x] == 3){
	cout << s.cnt<<endl;
	flag = false;
	break;
      }
      reset();
      dfs(s.px, s.py, s.x, s.y);
      rep(i, 4){
	State now = s;
	int nx = s.x + dx[i], ny = s.y + dy[i];
	int px = s.x - dx[i], py = s.y - dy[i];
	if(ny < 0 || nx < 0 || ny >= h || nx >= w)continue;
	if(py < 0 || px < 0 || py >= h || px >= w)continue;
	if(t[ny][nx] == 1 || !can[py][px])continue;
	if(visited[ny][nx][py][px])continue;
	visited[ny][nx][py][px] = true;
	now.x = nx;
	now.y = ny;
	now.px = px;
	now.py = py;
	now.cnt++;
	Q.push(now);
      }
    }
    if(flag)cout << -1 << endl;
  }
}

すっきりかけた。
ただ、ステートで記憶する状態は元来た方向でよかったし、
visitedも押された方向でよかった。
でも、修正せずにこのままでいった。