ＳＬＧの移動力を求める式について

[コーイチ]

http://www5f.biglobe.ne.jp/~kenmo/progr ... ve.html#2a
こちらのサイトを参考にＳＬＧを作ろうとしているのですが、
どうも思い通りに動いてくれません。
（どうやら０と１を交互に書き込んでいるようです）
どのようにしたら上記のサイトのように動くのか教えてください。
（配列の添え字チェックは省いています。）

コード:

#include <stdio.h>
#include <string>

int gMove = 4;			// 移動力
const int WIDTH = 10, HEIGHT = 10;
char gMap[WIDTH][HEIGHT];
int gX = 5, gY = 5;

void setStart(int x, int y)
{
	gMap[x][y] = gMove;
}

void printMap()
{
	std::string str;
	char buf[8];
	for (int i = 0; i < HEIGHT; i++)
	{
		for (int j = 0; j < WIDTH; j++)
		{
			sprintf_s(buf, "%-2d", gMap[j][i]);
			str += buf;
		}
		str += "\n";
	}
	str += "-------------------------\n";
	printf("%s", str.c_str());
}

void Search4(int x, int y, int m);

void Search(int x, int y, int m)
{
	int t = m;

	if (gMap[x][y] < t)
		t += gMap[x][y];

	if (t > gMap[x][y])
	{
		gMap[x][y] = t;
	}

	if (t > 0)
		Search4(x, y, t);
}

void Search4(int x, int y, int m)
{
	printMap();
	Search(x, y - 1, m);
	Search(x, y + 1, m);
	Search(x + 1, y, m);
	Search(x - 1, y, m);
}

int main(int argc, char* argv[])
{
	for (int i = 0; i < HEIGHT; i++)
	{
		for (int j = 0; j < WIDTH; j++)
		{
			gMap[j][i] = -1;
		}
	}

	setStart(gX, gY);
	Search4(gX, gY, gMove);

	getchar();

	return 0;
}

[みけCAT]

どのようにしたら上記のサイトのように動くのか教えてください。

サイトの仕様と同じかはわかりませんが、こうするといい感じの動作になりそうだと思います。

コード:

#include <stdio.h>
#include <string>

// 追加。もしC++を使いたいなら、sprintfに対応していないコンパイラは使わないことをおすすめします。
#define sprintf_s sprintf

int gMove = 4;			// 移動力
// 狭すぎてはみ出すので修正
// const int WIDTH = 10, HEIGHT = 10;
const int WIDTH = 11, HEIGHT = 11;
char gMap[WIDTH][HEIGHT];
char gMap_orig[WIDTH][HEIGHT]; // 追加
int gX = 5, gY = 5;

void setStart(int x, int y)
{
	gMap[x][y] = gMove;
}

// 追加
void saveMap() {
	for (int i = 0; i < HEIGHT; i++)
	{
		for (int j = 0; j < WIDTH; j++)
		{
			gMap_orig[j][i] = gMap[j][i];
		}
	}
}

void printMap()
{
	std::string str;
	char buf[8];
	for (int i = 0; i < HEIGHT; i++)
	{
		for (int j = 0; j < WIDTH; j++)
		{
			sprintf_s(buf, "%-2d", gMap[j][i]);
			str += buf;
		}
		str += "\n";
	}
	str += "-------------------------\n";
	printf("%s", str.c_str());
}

void Search4(int x, int y, int m);

void Search(int x, int y, int m)
{
	int t = m;

/*
	if (gMap[x][y] < t)
		t += gMap[x][y];

	if (t > gMap[x][y])
	{
		gMap[x][y] = t;
	}

	if (t > 0)
		Search4(x, y, t);
*/
	// 直感的に普通に書こう
	if (t > gMap[x][y]) {
		// 初めて移動するか前より効率よく移動できたら、結果を更新する
		gMap[x][y] = t;
		int next = t + gMap_orig[x][y];
		if (next >= 0) {
			// まだ移動できるなら、探索続行する
			Search4(x, y, next);
		}
	}
}

void Search4(int x, int y, int m)
{
	printMap();
	Search(x, y - 1, m);
	Search(x, y + 1, m);
	Search(x + 1, y, m);
	Search(x - 1, y, m);
}

int main(int argc, char* argv[])
{
	for (int i = 0; i < HEIGHT; i++)
	{
		for (int j = 0; j < WIDTH; j++)
		{
			gMap[j][i] = -1;
		}
	}

	// 移動力が重複するので削除
	// setStart(gX, gY);
	saveMap(); // 追加、地形データを保存する
	Search4(gX, gY, gMove);
	printMap(); // 最終結果を表示するため追加

	getchar();

	return 0;
}

オフトピック

std::queueを使って幅優先探索しよう(提案)
【訂正】幅優先探索よりダイクストラ法の方がいいです。

[コーイチ]

返信ありがとうございます。
なるほど、もとの配列のコピーを用意すればよかったんですね。

ただ、現在は問題なく動いていますが、
参考にしたサイトのように、移動不可の地形や１つ進むたびに移動力が２減るような
地形を作成してもうまく動きません。

コード:

for (int i = 0; i < HEIGHT; i++)
{
	for (int j = 0; j < WIDTH; j++)
	{
		gMap[j][i] = -1;
	}
}
gMap[4][4] = -2; // 移動力が２減るマス
gMap[6][7] = -9; // 移動不可

こういった機能を実装するにはどのようにコードを書けばいいのでしょうか？
また、std::queueを使用して幅優先検索をするというのはどういう事でしょうか？

[みけCAT]

ただ、現在は問題なく動いていますが、
参考にしたサイトのように、移動不可の地形や１つ進むたびに移動力が２減るような
地形を作成してもうまく動きません。

すいません、確認不足でした。
これでどうでしょうか？

コード:

#include <stdio.h>
#include <string>

// 追加。もしC++を使いたいなら、sprintfに対応していないコンパイラは使わないことをおすすめします。
#define sprintf_s sprintf

int gMove = 4;			// 移動力
// 狭すぎてはみ出すので修正
// const int WIDTH = 10, HEIGHT = 10;
const int WIDTH = 11, HEIGHT = 11;
char gMap[WIDTH][HEIGHT];
char gMap_orig[WIDTH][HEIGHT]; // 追加
int gX = 5, gY = 5;

void setStart(int x, int y)
{
	gMap[x][y] = gMove;
}

// 追加
void saveMap() {
	for (int i = 0; i < HEIGHT; i++)
	{
		for (int j = 0; j < WIDTH; j++)
		{
			gMap_orig[j][i] = gMap[j][i];
		}
	}
}

void printMap()
{
	std::string str;
	char buf[8];
	for (int i = 0; i < HEIGHT; i++)
	{
		for (int j = 0; j < WIDTH; j++)
		{
			sprintf_s(buf, "%-2d", gMap[j][i]);
			str += buf;
		}
		str += "\n";
	}
	str += "-------------------------\n";
	printf("%s", str.c_str());
}

void Search4(int x, int y, int m);

void Search(int x, int y, int m)
{
	int t = m;

/*
	if (gMap[x][y] < t)
		t += gMap[x][y];

	if (t > gMap[x][y])
	{
		gMap[x][y] = t;
	}

	if (t > 0)
		Search4(x, y, t);
*/
	// 直感的に普通に書こう
	int next = t + gMap_orig[x][y]; // ここのコストを引いた後の移動力
	if (next >= 0 && next > gMap[x][y]) {
		// 移動でき、かつ初めて移動するか前より効率がよかったら、結果を更新する
		gMap[x][y] = next;
		Search4(x, y, next);
	}
}

void Search4(int x, int y, int m)
{
	printMap();
	Search(x, y - 1, m);
	Search(x, y + 1, m);
	Search(x + 1, y, m);
	Search(x - 1, y, m);
}

int main(int argc, char* argv[])
{
	for (int i = 0; i < HEIGHT; i++)
	{
		for (int j = 0; j < WIDTH; j++)
		{
			gMap[j][i] = -1;
		}
	}

	gMap[4][4] = -2; // 移動力が２減るマス
	gMap[6][7] = -9; // 移動不可

	// 移動力が重複するので削除
	// setStart(gX, gY);
	saveMap(); // 追加、地形データを保存する
	// *訂正* : Search4ではなくSearchを呼ぶ
	Search(gX, gY, gMove - gMap_orig[gX][gY]); // スタート位置の移動力減少分を打ち消す
	printMap(); // 最終結果を表示するため追加

	getchar();

	return 0;
}

また、std::queueを使用して幅優先検索をするというのはどういう事でしょうか？

そのままの意味です。

[コーイチ]

返信ありがとうございます。
おかげでうまくいきました。

「幅優位検索」という単語で検索してみて、
アルゴリズム自体は複雑そうではないのですが、
これを先ほどのコードで利用する方法が分かりません。
（応用の仕方が分かりません。）

考え方だけでも教えてください。

[みけCAT]

Search関数が深さ優先探索のプログラムになっているので、これを幅優先探索にするということです。
ただし、コストが一定ではないので、幅優先探索ではなくプライオリティキューから残り移動力の多い順に取り出すダイクストラ法の方がいいと思います。

[コーイチ]

うーん……私には難しいです。
プライオリティキューを使用したダイクストラ法を使用すると、
コードの速度が速くなったり、可読性が高まったりしますか？

もしよければ、サンプルのコードを張ってもらえると助かります。
そのコードを読んでアルゴリズムについて勉強しようと思います。

[みけCAT]

プライオリティキューを使用したダイクストラ法を使用すると、
コードの速度が速くなったり、可読性が高まったりしますか？

微妙だと思います。

もしよければ、サンプルのコードを張ってもらえると助かります。

コード:

#include <stdio.h>
#include <string>
#include <queue>

int gMove = 4;			// 移動力
const int WIDTH = 11, HEIGHT = 11;
char gMap[WIDTH][HEIGHT];
char gMap_orig[WIDTH][HEIGHT];
int gX = 5, gY = 5;

void saveMap() {
	for (int i = 0; i < HEIGHT; i++)
	{
		for (int j = 0; j < WIDTH; j++)
		{
			gMap_orig[j][i] = gMap[j][i];
		}
	}
}

void printMap()
{
	std::string str;
	char buf[8];
	for (int i = 0; i < HEIGHT; i++)
	{
		for (int j = 0; j < WIDTH; j++)
		{
			sprintf(buf, "%-2d", gMap[j][i]);
			str += buf;
		}
		str += "\n";
	}
	str += "-------------------------\n";
	printf("%s", str.c_str());
}

struct SearchStatus
{
	int x, y;
	int powerLeft;

	SearchStatus(int xx = 0, int yy = 0, int pl = 0) : x(xx), y(yy), powerLeft(pl) {}
	bool operator<(const SearchStatus& ss) const
	{
		return powerLeft < ss.powerLeft;
	}
};

void Search(int x, int y, int m)
{
	// 移動の種類
	static const int d[4][2] = {
		{0, -1}, {0, 1}, {1, 0}, {-1, 0}
	};

	std::priority_queue<SearchStatus> q;
	q.push(SearchStatus(x, y, m));
	while (!q.empty())
	{
		// 残り移動力が最大の状態を取得する
		SearchStatus ss = q.top();
		q.pop();
		if (gMap[ss.x][ss.y] >= 0) continue; // 既に探索した場所は無視する
		// 情報を決定する
		gMap[ss.x][ss.y] = ss.powerLeft;
		printMap();
		// 次の場所へ行く
		for (int i = 0; i < 4; i++)
		{
			// 次の座標を取得する
			int nx = ss.x + d[i][0];
			int ny = ss.y + d[i][1];
			// 次の座標がはみ出していないなら
			if (nx >= 0 && ny >= 0 && nx < WIDTH && ny < HEIGHT)
			{
				// 次の移動力を取得し、移動できるなら探索対象に追加する
				int np = ss.powerLeft + gMap_orig[nx][ny];
				if (np >= 0) q.push(SearchStatus(nx, ny, np));
			}
		}
	}
}

int main(void)
{
	for (int i = 0; i < HEIGHT; i++)
	{
		for (int j = 0; j < WIDTH; j++)
		{
			gMap[j][i] = -1;
		}
	}

	gMap[4][4] = -2; // 移動力が２減るマス
	gMap[6][7] = -9; // 移動不可

	saveMap(); // 地形データを保存する
	Search(gX, gY, gMove);

	return 0;
}

[コーイチ]

返信ありがとうございます。

なるほど、確かにコードにしてみるとそこまで複雑ではないんですね。
数値の大きい順に書き込まれるようになっていることも確認できました。

うーん、これでＳＬＧの移動力を求める式が完成しましたかね？
実際に使用するにはもう少しコードを書き換える必要がありそうですが。