AOJ 0121 Seven Game

AOJ 幅優先探索

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;

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

AOJ 0558 Cheese

AOJ 幅優先探索

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回目だというのに、まだ蟻本無しで書ききろうとすると、もの凄く時間がかかる。
この辺のスピードアップが今後の課題ですね。

AOJ 0179 Mysterious Worm

AOJ 幅優先探索

初めて記事を書くことになります。
これからいろんな問題を解いて、その感想やらを書き綴りながらアルゴリズムをマスターしていきたいところ。

                                            • -

AOJ 0179 Mysterious Worm

id:kyuridenamida さんの

http://d.hatena.ne.jp/kyuridenamida/20111009/1318087144

こちらから幅優先探索の問題を解いてみた。

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

typedef pair<string, int> P;

int bfs(string worm){
	queue<P> que;
	que.push(P(worm, 0));

	map<string, int> d;
	
	while(!que.empty()){
		P p = que.front();
		que.pop();

		//重複パターンはcontinue
		if(d[p.first]) continue;

		string str = p.first;

		//全色同じかどうかのチェック
		bool flag = false;
		for(int i=0;i<str.size()-1;i++){
			if(str[i] != str[i+1]){
				flag = true;
				break;
			}
		}
		//同じならreturn
		if(!flag) return p.second;

		//重複パターン判別用
		d[p.first] = p.second;

		for(int i=0;i<str.size()-1;i++){
			//隣り合わせで色が異なるとき
			if(str[i] != str[i+1]){
				char temp;
				string next;

				//tempに含まれない一色を代入
				if(str[i] != 'b' && str[i+1] != 'b'){
					temp = 'b';
				}else if(str[i] != 'g' && str[i+1] != 'g'){
					temp = 'g';
				}else{
					temp = 'r';
				}

				//変化後の順番をnextに詰め込む
				next = str;
				next[i] = next[i+1] = temp;

				//キューにプッシュ
				que.push(P(next, p.second+1));
			}
		}
	}
	return -1;
}

int main(){
	string worm;
	while(cin >> worm && worm != "0"){
		int ret = bfs(worm);
		if(ret>=0) cout << ret << endl;
		else cout << "NA" << endl;
	}
}

mapに対して[]演算子で存在しないものを参照すると自動で生成されるということを初めて知りました。

あとは、今まで殆ど使ってなかったtypedefに慣れるいい機会になった。かな。