AOJ 0558 Cheese

AOJ 0558 Cheese

昨日に引き続き幅優先探索の問題を見つけてきて解いてみた。

#include <iostream>
#include <queue>
#include <map>
#define INF 10000000
using namespace std;

typedef pair<int, int> P;

int H, W, N;
int d[1000][1000];
char cell[1000][1000];
int si, sj, sum = 0;

void bfs(P start, int search){
	//4方向用
	int vi[4] = {0, 0, -1, 1}, vj[4] = {-1, 1, 0, 0};

	int gi, gj;

	//最短距離をINFに初期化し、さらにゴールの座標を取得
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			d[i][j] = INF;
			if(cell[i][j] == search + '0'){
				gi = i;
				gj = j;
			}
		}
	}

	//startは最短距離0に初期化
	d[start.first][start.second] = 0;

	queue<P> que;
	que.push(start);

	while(!que.empty()){
		P p = que.front();
		que.pop();

		//一致でbreak
		if(p.first == gi && p.second == gj) break;

		//next(i, j)
		int ni, nj;

		//4方向分
		for(int i=0;i<4;i++){
			ni = p.first + vi[i];
			nj = p.second + vj[i];

			if(ni >= 0 && ni < H && nj >= 0 && nj < W && cell[ni][nj] != 'X' && d[ni][nj] == INF){
				que.push(P(ni, nj));
				d[ni][nj] = d[p.first][p.second] + 1;
			}
		}
	}

	sum += d[gi][gj];

	if(search != N)	bfs(P(gi, gj), search+1);
}

int main(){
	cin >> H >> W >> N;

	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			cin >> cell[i][j];
			if(cell[i][j] == 'S'){
				si = i;
				sj = j;
			}
		}
	}
	
	bfs(P(si, sj), 1);

	cout << sum << endl;
}

眠い中書いたからゴチャゴチャしていることを除けば、まあ前回のAOJ 0179 Mysterious Wormと構造としてはほとんど同じかな。
違うのは、最後の数字に辿り続くまで再帰させて、その都度グローバル関数のsumに足し込むってぐらい。

ほとんど似たようなコードを書くのこれで3回目だというのに、まだ蟻本無しで書ききろうとすると、もの凄く時間がかかる。
この辺のスピードアップが今後の課題ですね。