ぱーぽーの競プロ記

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

AOJ 1140 Cleaning Robot

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


・概要
ロボットが部屋の汚れたタイルを全部掃除し終わるまでの最短移動数を求める問題です。

入力として、ロボットの位置と汚れたタイル、綺麗なタイル、障害物が与えられます。


・解法
幅優先探索で解くことができます。

汚れているマスの数をビットで表現すると簡単に解くことができます。
int minCost[20][20][(1 << 10)];


ソースコード

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

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

static const int dx[]={1,-1,0,0};
static const int dy[]={0,0,1,-1};
static const int INF = (1 << 29);

struct State{
   int x, y, cost, unvisit;
   State(int x, int y, int c, int u):x(x),y(y),cost(c),unvisit(u){}
};

int w,h,dustNum;
int sx, sy;
int dustID[20][20];
int minCost[20][20][(1 << 10)];
char G[20][20];

int bfs(){
   rep(i,20)rep(j,20)rep(k,(1<<10))minCost[i][j][k] = INF;
   queue<State>q;
   q.push(State(sx, sy, 0, (1 << dustNum)-1));
   
   while(!q.empty()){
      State p = q.front();
      q.pop();

      if(p.unvisit==0)return p.cost;

      if(minCost[p.x][p.y][p.unvisit] <= p.cost)continue;
      minCost[p.x][p.y][p.unvisit] = p.cost;

      for(int k = 0 ; k < 4 ; k++){
	 int nx = p.x + dx[k];
	 int ny = p.y + dy[k];
	 
	 if(0<=nx&&nx<h && 0<=ny&&ny<w && G[nx][ny]!='x'){
	    if(G[nx][ny]=='*'){
	       int next = p.unvisit & ~(1 << dustID[nx][ny]);
	       q.push(State(nx, ny, p.cost+1, next));
	    }
	    else{
	       q.push(State(nx, ny, p.cost+1, p.unvisit));
	    }
	 }
      }
   }
   return -1;
}
   
int main(){
   while(cin >> w >> h){
      if(w==0 && h==0)break;

      memset(dustID,-1,sizeof(dustID));
      dustNum = 0;

      rep(i,h){
	 rep(j,w){
	    cin >> G[i][j];
	    if(G[i][j]=='o'){
	       sx = i; sy = j;
	       G[i][j] == '.';
	    }
	    if(G[i][j]=='*'){
	       dustID[i][j] = dustNum++;
	    }
	 }
      }
      
      cout << bfs() << endl;
   }
   return 0;
}