PE Problem 83

Project Euler Problem 83

PEの解いていない問題の中から、幅優先探索っぽい問題を探し出して解いてみた。
幅優先探索で解いたとはいえ、実際は距離というより合計値がキーになってくる問題。
うまく枝刈りをしていって、１分以内に終わるようにしました。
大したことしてないけど。

#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#define INF 10000000
#define MAX 80
#define FOR(a,start,end) for(long long int a=(start);a<(end);++a)
using namespace std;

//現在の場所用構造体
struct cell{
	int i;
	int j;
};

typedef pair<cell, int> P;

int mat[MAX][MAX];	//入力された行列
int d[MAX][MAX];	//合計値の暫定最小値テーブル

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

	FOR(i, 0, MAX){
		FOR(j, 0, MAX){
			d[i][j] = INF;
		}
	}

	queue<P> que;

	cell obj;
	obj.i = 0;
	obj.j = 0;

	que.push(pair<cell, int>(obj, 0));


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

		int i = p.first.i;
		int j = p.first.j;
		int sum = p.second + mat[i][j];

		//(i, j)までの合計値が更新される時
		if(sum < d[i][j]){
			d[i][j] = sum;

			//右下についたらこれ以上探索しない
			if(i == MAX-1 && j == MAX-1) continue;

			//next_i, next_j
			int ni, nj;
			FOR(k, 0, 4){
				ni = i + vi[k];
				nj = j + vj[k];
				
				if(ni < 0 || ni >= MAX || nj < 0 || nj >= MAX) continue;

				//push用の構造体
				cell new_obj;
				new_obj.i = ni;
				new_obj.j = nj;

				que.push(pair<cell, int>(new_obj, sum));
			}
		}
	}

	return d[MAX-1][MAX-1];
}

int main(){
	FILE *fp;
	fp = fopen("083_txt.txt", "r");

	FOR(i, 0, MAX){
		FOR(j, 0, MAX){
			fscanf(fp, "%d", &mat[i][j]);
			if(j != MAX) fscanf(fp, "%*c");
		}
	}

	cout << bfs() << endl;

	fclose(fp);
}

実は、最小値テーブルが更新されたら、更新するようなルート以外の探索をすぐ終わるべきなんだけれども、
それをしない状態で試しに実行してみたところ割りと早く終わったので枝刈りしませんでした。
というか、実装しようと思ったけど若干面倒臭そうだったのでやめました。

今回新しくやったことといったら、構造体をpairの要素として持たせたってことぐらいですかね。

最初pairにpairを要素として持たせたら、何故かうまくコンパイルができませんでした…。
ちゃんと出来るのであればやったのですが、よくわからず。
どうやるんだろうか…。