AOJ 0121 Seven Game

まずは前回、前々回の問題に引き続きただただ幅優先探索をしようと思ってコードを書き上げた。
サンプルデータをぶち込んでみて、特に問題無さそうだったので、Submitしてみると、見事Time Limit Exceeded。時間オーバー。

毎回毎回探索していることで、多くのデータを通す時には時間がかかってしまい、TLEを食らってしまうらしい。

どうにかできないものかと思って、逆方向から探索をしてみることにしました。
つまりどういうことかというと、完成形である"01234567"の状態から遷移できる、全状態への最短手順を幅優先探索を用いて出してしまおうというもの。
一度計算してしまえば、あとは対にしておいたmapを参照してしまえば終わり、という感じ。

入力は、行を読み込んで、スペースを排除して、それから使うといった感じ。

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

int main(){
	//4方向用配列
	int vec[] = {1, -1, 4, -4};
	queue<string> que;
	que.push("01234567");

	//探索済みテーブル
	map<string, int> d;

	//"01234567"から逆向きに幅優先探索しながら探索済みテーブルを埋める
	while(!que.empty()){
		string str = que.front();
		que.pop();
		int zero = str.find("0");

		string str2;
		FOR(i, 0, 4){
			int next_z;
			next_z = zero + vec[i];
			if(next_z >= 0 && next_z <= 7 && !((zero == 3 && next_z == 4) || (zero == 4 && next_z == 3))){
				str2 = str;
				swap(str2[zero], str2[next_z]);
				if(d.find(str2) == d.end()){
					que.push(str2);
					d[str2] = d[str] + 1;
				}
			}
		}
	}

	//入力から' 'を除いて探索済みテーブルから答えを出力
	string num;
	while(getline(cin, num)){
		string::iterator end_it = remove(num.begin(), num.end(), ' ');
		num.erase(end_it, num.end());
		cout << d[num] << endl;
	}
}

これを通すまでに、実は別のコードを提出してWAを食らってました。

  1 2 3 0←
→4 5 6 7

具体的には、上みたいな状態で、0と4を入れ替えられてしまうようなコードを提出していました。
１次元配列で考えているとやってしまうミス。

今回は、競技プログラマーがよくやってるfor文の#define

#define FOR(a,start,end) for(I64 a=(start);a<(end);a++)

を試しに使って見ました。
I64は一つ上にあるけどlong long int
でも、これは型なので、次からは多分

#define FOR(a,start,end) for(long long int a=(start);a<(end);a++)

に変えて、下の方に

typedef long long int I64;

とかすると思う。
そんだけ。