DFS再帰アルゴリズムc++実装----インスタンス迷宮問題

2417 ワード
最近DFSアルゴリズムを使う必要があるので、ネット上で関連資料を探して、文の中のコードは以下のブログを参考にして、いくつか修正しました.
https://www.cnblogs.com/majianqiang/p/8534418.html------ブログサイトを参考に
修正内容:
1.迷宮問題では2次元配列の最も左の位置が入口であり、最も右の位置が出口であると規定されている.右端に到達すると検索が終了します.
2.pathは検索パスを保存した
#include
#include
#include
#include
#include
#include

#define MAXL 5

using namespace std;

bool isValid(vector >& maze, int x, int y) {
	return !maze[x][y];
}

bool maze_search(vector >& maze, bool(*visit)[MAXL], pair& pos, vector>&path) {

	if (pos.first == (MAXL - 1) && pos.second == (MAXL - 1))
		return true;

	int dir[][2] = { { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 } };
	for (int i = 0; i < 4; i++) {
		int vx = pos.first + dir[i][0];
		int vy = pos.second + dir[i][1];
		pair pos_dir(vx, vy);

		if ((vx >= 0 && vx < MAXL && vy >= 0 && vy < MAXL) && isValid(maze, vx, vy) && !visit[vx][vy]) {
			visit[vx][vy] = true;
			path.push_back(make_pair(vx, vy));
			if (maze_search(maze, visit, pos_dir, path))
				return true;
		}
	}

	path.pop_back();
	visit[pos.first][pos.second] = false;
	return false;
}

void display_2_vector(vector >& ivec) {
	for (int i = 0; i < ivec.size(); i++) {
		for (int j = 0; j < ivec[0].size(); j++) {
			cout << ivec[i][j] << " ";
		}
		cout << endl;
	}
}

int main(void)
{
	int a[MAXL][MAXL] = { { 0, 1, 1, 1, 1 }, { 0, 0, 0, 1, 1 }, { 0, 1, 1, 1, 1 }, { 0, 0, 0, 1, 1 }, { 0, 0, 0, 0, 0 } };
	vector > maze(MAXL, vector(MAXL));
	for (int i = 0; i < MAXL; i++) {
		for (int j = 0; j < MAXL; j++) {
			maze[i][j] = a[i][j];
		}
	}
	bool visit[MAXL][MAXL] = { { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0 }, {0,0,0,0,0},{ 0, 0, 0, 0, 0 } };
	visit[0][0] = 1;
	vector>path;
	pairpos_start(0, 0);
	path.push_back(pos_start);
	maze_search(maze, visit, pos_start, path);
	display_2_vector(maze);
	cout << endl;
	for (int i = 0; i < MAXL; i++) {
		for (int j = 0; j < MAXL; j++)
			cout << visit[i][j] << " ";
		cout << endl;
	}

	system("pause");
}

Gradle 3-簡単な説明
Macからcolorfulboxのレンタルサーバーにssh接続した手順