横型探索（８パズル）

/*********************************/
/* 横型探索（８パズル）          */
/*           coded by Y.Suganuma */
/*********************************/
#include <stdio.h>
#include <queue>
#include <map>
#include <string>
using namespace std;

class Depth
{
	public:
		int dep;
		string prev;
		Depth (string str, int dep1)
		{
			prev = str;   // 前の状態
			dep  = dep1;   // 深さ
		}
};

/********************************/
/* コマの移動                   */
/*      str : 現在の状態        */
/*      res : 移動後の状態      */
/*      return : 移動後の状態数 */
/********************************/
int move(string str, string *res)
{
	int k, n = 0;
	string str1;

	k = str.find("0");
	switch(k) {
		case 0:
			str1   = str.replace(k, 1, str, k+3, 1);
			str1   = str1.replace(k+3, 1, 1, '0');
			res[n] = str1;
			n++;
			str1   = str.replace(k, 1, str, k+1, 1);
			str1   = str1.replace(k+1, 1, 1, '0');
			res[n] = str1;
			n++;
			break;
		case 1:
			str1   = str.replace(k, 1, str, k+3, 1);
			str1   = str1.replace(k+3, 1, 1, '0');
			res[n] = str1;
			n++;
			str1   = str.replace(k, 1, str, k-1, 1);
			str1   = str1.replace(k-1, 1, 1, '0');
			res[n] = str1;
			n++;
			str1   = str.replace(k, 1, str, k+1, 1);
			str1   = str1.replace(k+1, 1, 1, '0');
			res[n] = str1;
			n++;
			break;
		case 2:
			str1   = str.replace(k, 1, str, k+3, 1);
			str1   = str1.replace(k+3, 1, 1, '0');
			res[n] = str1;
			n++;
			str1   = str.replace(k, 1, str, k-1, 1);
			str1   = str1.replace(k-1, 1, 1, '0');
			res[n] = str1;
			n++;
			break;
		case 3:
			str1   = str.replace(k, 1, str, k-3, 1);
			str1   = str1.replace(k-3, 1, 1, '0');
			res[n] = str1;
			n++;
			str1   = str.replace(k, 1, str, k+3, 1);
			str1   = str1.replace(k+3, 1, 1, '0');
			res[n] = str1;
			n++;
			str1   = str.replace(k, 1, str, k+1, 1);
			str1   = str1.replace(k+1, 1, 1, '0');
			res[n] = str1;
			n++;
			break;
		case 4:
			str1   = str.replace(k, 1, str, k-3, 1);
			str1   = str1.replace(k-3, 1, 1, '0');
			res[n] = str1;
			n++;
			str1   = str.replace(k, 1, str, k+3, 1);
			str1   = str1.replace(k+3, 1, 1, '0');
			res[n] = str1;
			n++;
			str1   = str.replace(k, 1, str, k-1, 1);
			str1   = str1.replace(k-1, 1, 1, '0');
			res[n] = str1;
			n++;
			str1   = str.replace(k, 1, str, k+1, 1);
			str1   = str1.replace(k+1, 1, 1, '0');
			res[n] = str1;
			n++;
			break;
		case 5:
			str1   = str.replace(k, 1, str, k-3, 1);
			str1   = str1.replace(k-3, 1, 1, '0');
			res[n] = str1;
			n++;
			str1   = str.replace(k, 1, str, k+3, 1);
			str1   = str1.replace(k+3, 1, 1, '0');
			res[n] = str1;
			n++;
			str1   = str.replace(k, 1, str, k-1, 1);
			str1   = str1.replace(k-1, 1, 1, '0');
			res[n] = str1;
			n++;
			break;
		case 6:
			str1   = str.replace(k, 1, str, k-3, 1);
			str1   = str1.replace(k-3, 1, 1, '0');
			res[n] = str1;
			n++;
			str1   = str.replace(k, 1, str, k+1, 1);
			str1   = str1.replace(k+1, 1, 1, '0');
			res[n] = str1;
			n++;
			break;
		case 7:
			str1   = str.replace(k, 1, str, k-3, 1);
			str1   = str1.replace(k-3, 1, 1, '0');
			res[n] = str1;
			n++;
			str1   = str.replace(k, 1, str, k-1, 1);
			str1   = str1.replace(k-1, 1, 1, '0');
			res[n] = str1;
			n++;
			str1   = str.replace(k, 1, str, k+1, 1);
			str1   = str1.replace(k+1, 1, 1, '0');
			res[n] = str1;
			n++;
			break;
		case 8:
			str1   = str.replace(k, 1, str, k-3, 1);
			str1   = str1.replace(k-3, 1, 1, '0');
			res[n] = str1;
			n++;
			str1   = str.replace(k, 1, str, k-1, 1);
			str1   = str1.replace(k-1, 1, 1, '0');
			res[n] = str1;
			n++;
			break;
	}

	return n;
}

/*************************/
/* 横型探索（８パズル）  */
/*      start : 初期状態 */
/*      goal : 目標状態  */
/*************************/
void width(string start, string goal)
{
	int i1, n, node1 = 1, node2 = 0, dep = 1, ct = 1;
	string str, res[4];
	queue<pair<string, int> > q;
	map<string, Depth> m;
	map<string, Depth>::iterator it;

	m.insert(pair<string, Depth>(start, Depth("",dep)));
	q.push(pair<string, int>(start, dep));
	while (!q.empty()) {
		str = q.front().first;
		dep = q.front().second;
		node2++;
					// ゴール
		if (str == goal) {
			ct = dep;
			break;
		}
					// ゴールでない
					// コマを移動し，同じ状態のものがなければキューに追加
		else {
			q.pop();
			n = move(str, res);
			for (i1 = 0; i1 < n; i1++) {
				it = m.find(res[i1]);   // 同じ状態か？
				if (it == m.end()) {
					m.insert(pair<string, Depth>(res[i1], Depth(str,dep+1)));
					q.push(pair<string, int>(res[i1], dep+1));
					node1++;
				}
			}
		}
	}
					// 結果の出力
	printf("   展開とチェック： %d %d，　最短距離： %d\n", node1, node2, ct);
	while (str.length() > 0) {
		printf("\n      %c %c %c\n", str.at(0), str.at(1), str.at(2));
		printf("      %c %c %c\n", str.at(3), str.at(4), str.at(5));
		printf("      %c %c %c\n", str.at(6), str.at(7), str.at(8));
		it  = m.find(str);
		str = ((*it).second).prev;
	}
}

int main()
{
	string goal = "123804765";

	printf("例１\n");
	string start = "283164705";
	width(start, goal);

	printf("例２\n");
	start = "216408753";
	width(start, goal);

	return 0;
}