AOJ - Problem 0558 : Cheese

• 問題文

1,2, ... , NのチーズがN個あり、1から順に食べるとき全部のチーズを食べるのに必要な最短経路を求める問題です(Nは9以下)。必ず全てのチーズが食べられることが保証されているようです。またフィールドの幅と高さw,hは1000以下となっています。

幅優先探索(BFS)で解くことのできる問題です。スタートからチーズ1まで最短経路、チーズ1からチーズ2までの最短経路, ... , チーズn-1からチーズnまでの最短経路とそれぞれ求めましょう。

探索するときは配列dについてd[y][x]にスタートから(x,y)まで最短経路の値を入れるようにします。初めに配列dのすべてのマスのINF(非常に大きい数)で初期化し、INFをまだ探索していないマスとして扱います。スターとから順に探索し、探索していないマス(値がINF)だったらその都度配列dの値を更新します。

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

struct p{
	int x, y;
};
typedef struct p P;
const int INF = 1e+7;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

int w,h,n;
string m[1001];
P cheese[11];
int ans = 0;
int d[1001][1001];

void bfs(){
	for(int i=1 ; i <= n ; i++ ){
		P sp = cheese[i-1];
		int sx = cheese[i-1].x;
		int sy = cheese[i-1].y;
		int gx = cheese[i].x;
		int gy = cheese[i].y;
		for(int y=0 ; y < h ; y++ ){
			for(int x=0 ; x < w ; x++ ){
				d[y][x] = INF;
			}
		}
		
		queue<P> q;
		q.push( sp );
		d[sy][sx] = 0;
		while( !q.empty() ){
			P now = q.front();
			q.pop();
			int x = now.x;
			int y = now.y;
			if( x == gx && y == gy ){
				ans += d[gy][gx];
				break;
			}
			for(int i=0 ; i < 4 ; i++ ){
				int mx = x + dx[i];
				int my = y + dy[i];
				if( mx < 0 || my < 0 || mx >= w || my >= h ) continue;
				if( m[my][mx] != 'X' ){
					P next;
					
					next.x = mx;
					next.y = my;
					if( d[my][mx] == INF ){
						d[my][mx] = d[y][x] + 1;
						q.push( next );
					}
				}
			}
		}
	}
}

int main(){
	cin >> h >> w >> n;
	for(int y=0 ; y < h ; y++ ){
		cin >> m[y];
	}
	
	
	for(int y=0 ; y < h ; y++ ){
		for(int x=0 ; x < w ; x++ ){
			char c = m[y][x];
			if( c == 'S' ){
				cheese[0].x = x;
				cheese[0].y = y;
			}
			if( c >= '1' && c <= '9' ){
				cheese[ c - '0' ].x = x;
				cheese[ c - '0' ].y = y;
			}
		}
	}
	bfs();
	cout << ans << endl;
}