ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 1218 Push!!

問題文はこちら↓
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1218


・概要
フィールド上のある場所からある場所まで人が箱を押して歩いた時の箱の最短経路を求める問題です。人はいくら動いてもよいです。

まずフィールドのサイズ(h x w)が与えられます。 (1<= h,w <= 7)
そのあとフィールド上の情報が以下のように与えられます。

0: 何も置いてない
1: 障害物
2: 箱
3: ゴール
4: 箱を押す人

ゴールできない場合は-1を出力します。


・解法
幅優先探索で解きます。
priority_queueには<所要時間、箱のある座標、人のいる座標>を持たせます。

また、箱を上下左右に移動させるためには人が押す側にいないといけません。 その判定を幅優先探索(bfs)か深さ優先探索(dfs)で毎回求める必要があります。(bfsとdfsの両方を試しましたが、どちらでも大丈夫みたいです)

例えば上の図の場合、箱は右、上、左には動かすことができます。
しかし下には動かすことができません。
下に動かすためには人が(0,1)に立たなければなりませんが、(0,0),(0,2)が塞がっているため行くことができないからです。


ソースコード

#include<iostream>
#include<cstring>
#include<queue>
#include<map>
#include<vector>
using namespace std;

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

#define f first
#define s second
#define mp make_pair
typedef pair<int, pair<pair<int,int>, pair<int,int> > > P;
//pair<minCost, pair<pair<cx, cy>, pair<wx, wy> > >

int w,h;
int cx,cy, wx,wy, gx,gy;
int G[7][7];
int minCost[7][7][7][7]; //minCost[cx][cy][wx][wy]
bool visited[7][7];
static const int INF = (1 << 29);
static const int dx[]={1,0,-1,0};
static const int dy[]={0,1,0,-1};//↓→↑←


bool canPeopleMove(int bx, int by, int ex, int ey, int tx, int ty){
   memset(visited,false,sizeof(visited));
   queue<pair<int, int> >q;
   q.push(mp(bx, by));
   
   while(!q.empty()){
      pair<int ,int> p = q.front();
      q.pop();
      
      if(p.f==ex && p.s==ey)return true;
      
      if(visited[p.f][p.s])continue;
      visited[p.f][p.s] = true;

      rep(k,4){
	 int nx = p.f + dx[k];
	 int ny = p.s + dy[k];
	 
	 if(0<=nx&&nx<h && 0<=ny&&ny<w && G[nx][ny]!=1 && !(tx==nx && ty==ny)){
	    q.push(mp(nx,ny));
	 }
      }
   }
   return false;
}

/*
void dfs(int x, int y, int tx, int ty){
   visited[x][y] = true;
   rep(k,4){
      int nx = x + dx[k];
      int ny = y + dy[k];
      if(0<=nx&&nx<h && 0<=ny&&ny<w && G[nx][ny]!=1 && !(tx==nx && ty==ny) && !visited[nx][ny]){
	 dfs(nx,ny,tx,ty);
      }
   }
}

bool canPeopleMove(int bx, int by, int ex, int ey, int tx, int ty){
   memset(visited,false,sizeof(visited));
   dfs(bx,by,tx,ty);
   return visited[ex][ey];
}
*/

int bfs(){
   rep(i,7)rep(j,7)rep(k,7)rep(l,7)minCost[i][j][k][l] = INF;
   priority_queue<P, vector<P>, greater<P> >pq;
   pq.push(mp(0, mp(mp(cx,cy), mp(wx,wy))));
   
   while(!pq.empty()){
      P p = pq.top();
      pq.pop();
      
      if(p.s.f.f==gx && p.s.f.s==gy)return p.f;
      
      if(minCost[p.s.f.f][p.s.f.s][p.s.s.f][p.s.s.s] <= p.f)continue;
      minCost[p.s.f.f][p.s.f.s][p.s.s.f][p.s.s.s] = p.f;

      rep(k,4){
	 int nx = p.s.f.f + dx[k];//cargo
	 int ny = p.s.f.s + dy[k];//cargo
	 int mx = p.s.f.f - dx[k];//man
	 int my = p.s.f.s - dy[k];//man

	 if(0<=nx&&nx<h && 0<=ny&&ny<w && 0<=mx&&mx<h && 0<=my&&my<w && G[nx][ny]!=1 && G[mx][my]!=1){
	    if(canPeopleMove(p.s.s.f, p.s.s.s, mx, my, p.s.f.f, p.s.f.s)){
	       pq.push(mp(p.f+1, mp(mp(nx,ny), mp(p.s.f.f,p.s.f.s))));
	    }
	 }
      }
   }
   return -1;
}

int main(){
   while(cin >> w >> h){
      if(w==0 && h==0)break;

      rep(i,h){
	 rep(j,w){
	    cin >> G[i][j];
	    if(G[i][j]==2){cx = i; cy = j;}
	    if(G[i][j]==3){gx = i; gy = j;}
	    if(G[i][j]==4){wx = i; wy = j;}
	 }
      }

      cout << bfs() << endl;
   }
   return 0;
}