以棧解決迷宮問題

    怎么找到一個迷宮的出口呢。首先要知道迷宮長啥樣，之后知道出入口，再之后就是找通路的過程了。

    顯然主要的部分是如何找通路。我們就舉一個例子：

    在這個迷宮中0就是墻，1就是路。那么我們可以用一個二維數組來表示這個迷宮。之后我們需要一種結構來實現我們表示位置的移動。

struct Pos
{
	size_t line;
	size_t row;
};

    這個結構體通過記錄行和列來表示現在處在迷宮的哪個位置。

    現在就可以開始進行找通路的過程了。我們很容易想到通過試探當前位置的周圍四個或三個位置來找到下一個應該去的位置，直到走到出口就算任務完成了。但是我們在試探的過程中，走到了下個位置，一定要把之前的位置做一個標記，否則我們的程序會一直在兩個位置之間走來走去。我們這里通過把之前的位置置為2來防止它走來走去。

                if (pos.row>0 && maze[pos.line * 10 + pos.row - 1] == 1)//左
		{
			p.push(pos.line * 10 + pos.row);
			pos.row--;
			maze[(pos.line * 10 + pos.row)] = 2;
		}
		else if (pos.row < 9 && maze[pos.line * 10 + pos.row + 1] == 1)//右
		{
			p.push(pos.line * 10 + pos.row);
			pos.row++;
			maze[(pos.line * 10 + pos.row)] = 2;
		}
		else if (pos.line > 0 && maze[(pos.line - 1) * 10 + pos.row] == 1)//上
		{
			p.push(pos.line * 10 + pos.row);
			pos.line--;
			maze[(pos.line * 10 + pos.row)] = 2;
		}
		else if (pos.line < 9 && maze[(pos.line + 1) * 10 + pos.row] == 1)//下
		{
			p.push(pos.line * 10 + pos.row);
			pos.line++;
			maze[(pos.line * 10 + pos.row)] = 2;
		}

    這段代碼就是對上下左右四個方向進行試探的過程，其中我們用一個棧記錄下了我們走過的位置，因為迷宮里面有岔路，所以我們走錯時需要進行回溯。而選用棧是因為棧的后進先出的特性。說到走進岔路進行回溯，當我們發現上面四種試探完成卻沒有通路時，就是我們已經走到了死胡同的最深處，需要進行回溯了，那末回溯的過程就是進行拿取棧頂元素，之后出棧的過程。

                        maze[(pos.line * 10 + pos.row)] = 3;
			pos.line = p.top() / 10;
			pos.row = p.top() - pos.line*10;
			p.pop();

    上面的代碼就是進行回溯的過程，再加一個是否到達終點的判斷就完成了主要部分。

                if (pos.line * 10 + pos.row == 91)
		{
			PrintMaze(maze);
			return 1;
		}

    上面就是找路徑的過程，也就是我們代碼的主要邏輯部分。剩下的就是一些注意事項。

    讀迷宮圖我是通過文件指針，fopen，fgets，fclose來實現的。之后在創建了一個二維數組之后我們給函數傳參的時候需要把它轉換成一個一級指針來傳遞。我們操作就把它當作一個一維數組來處理。因為在內存中一維數組和二維數組是一樣的，只不過表示方式不一樣而已，我們這個迷宮通過二維數組表示比較直觀，但是用一維數組一樣可以處理。

    下面是完整的代碼和運行的結果。

結果：

    可以看到上面的是最初的迷宮，經過我們走迷宮的過程，將走過的岔路標記為了3，正確的通路標記為了2。

    完整代碼：

#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<assert.h>
#include<stack>
using namespace std;

struct Pos
{
	size_t line;
	size_t row;
};

void InitMaze(int *maze)
{
	FILE *p = fopen("maze.txt", "r");
	for (int i = 0; i < 10; i++)
	{
		for (int j = 0; j < 10;)
		{
			int tmp =(int)(fgetc(p))-'0';
			if (tmp == 0)
				maze[i*10+j] = 0;

			if (tmp == 1)
				maze[i*10+j] = 1;

			if (tmp == 1 || tmp == 0)
				j++;
		}
	}

	fclose(p);
}

void PrintMaze(int *maze)
{
	for (int i = 0; i < 10; i++)
	{
		for (int j = 0; j < 10; j++)
		{
			cout << maze[i * 10 + j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}

int GoMaze(int *maze,Pos start)
{
	assert(maze);
	stack<int> p;
	
	Pos pos;
	pos.line = start.line;
	pos.row = start.row;

	while (1)
	{
		maze[(pos.line * 10 + pos.row)] = 2;

		if (pos.row>0 && maze[pos.line * 10 + pos.row - 1] == 1)//左
		{
			p.push(pos.line * 10 + pos.row);
			pos.row--;
			maze[(pos.line * 10 + pos.row)] = 2;
		}
		else if (pos.row < 9 && maze[pos.line * 10 + pos.row + 1] == 1)//右
		{
			p.push(pos.line * 10 + pos.row);
			pos.row++;
			maze[(pos.line * 10 + pos.row)] = 2;
		}
		else if (pos.line > 0 && maze[(pos.line - 1) * 10 + pos.row] == 1)//上
		{
			p.push(pos.line * 10 + pos.row);
			pos.line--;
			maze[(pos.line * 10 + pos.row)] = 2;
		}
		else if (pos.line < 9 && maze[(pos.line + 1) * 10 + pos.row] == 1)//下
		{
			p.push(pos.line * 10 + pos.row);
			pos.line++;
			maze[(pos.line * 10 + pos.row)] = 2;
		}
		else
		{
			maze[(pos.line * 10 + pos.row)] = 3;
			pos.line = p.top() / 10;
			pos.row = p.top() - pos.line*10;
			p.pop();
		}

		if (pos.line * 10 + pos.row == 91)
		{
			PrintMaze(maze);
			return 1;
		}
	}	
}

void Mazetest()
{
	int maze[10][10];
	Pos p;
	p.line = 2;
	p.row = 0;
	InitMaze((int *)maze);
	PrintMaze((int *)maze);
	GoMaze((int *)maze,p);
}

int main()
{
	Mazetest();
	return 0;
}