小青蛙有一天不小心落入了一個地下迷宮,小青蛙希望用自己僅剩的體力值P跳出這個地下迷宮。為了讓問 題簡單,假設這是一個n*m的格子迷宮,迷宮每個位置為0或者1,0代表這個位置有障礙物,小青蛙達到不了這個

題目：小青蛙有一天不小心落入了一個地下迷宮,小青蛙希望用自己僅剩的體力值P跳出這個地下迷宮。為了讓問

題簡單,假設這是一個n*m的格子迷宮,迷宮每個位置為0或者1,0代表這個位置有障礙物,小青蛙達到不了這個位

置;1代表小青蛙可以達到的位置。小青蛙初始在(0,0)位置,地下迷宮的出口在(0,m-1)(保證這兩個位置都是1,并

且保證一定有起點到終點可達的路徑),小青蛙在迷宮中水準移動一個機關距離需要消耗1點體力值,向上爬一個

機關距離需要消耗3個機關的體力值,向下移動不消耗體力值,當小青蛙的體力值等于0的時候還沒有到達出口,小

青蛙将無法逃離迷宮。現在需要你幫助小青蛙計算出能否用僅剩的體力值跳出迷宮(即達到(0,m-1)位置)。

輸入描述：

輸入包括n+1行:

第一行為三個整數n,m(3 <= m,n <= 10),P(1 <= P <= 100)

接下來的n行:

每行m個0或者1,以空格分隔

輸出描述：

如果能逃離迷宮,則輸出一行體力消耗最小的路徑,輸出格式見樣例所示;如果不能逃離迷宮,則輸出"Can not

escape!"。 測試資料保證答案唯一

示例1:

輸入

4 4 10 1 0 0 1 1 1 0 1 0 1 1 1 0 0 1 1

輸出

[0,0],[1,0],[1,1],[2,1],[2,2],[2,3],[1,3],[0,3]

#define VISITED 2//标記已經通路過的結點

int n;//n行
int m;//n列
int P;//p個力氣

int maze[10][10];//迷宮陣列

//假如一個坐标是(x,y),以下是坐标需要向左、右、上、下，坐标
//需要加的數，即如果向上走(x-1,y+0)
int dir[4][2] = { {0,-1},{0,1},{-1,0},{1,0} };

//向左、右、上、下分别需要加的體力值，如向上走，體力值需要
//減去3
int cost[4] = {-1,-1,-3,0};

int final_p = -200;//初始的體力剩餘值(初始較小，保證會被更新)

//坐标點
struct maze_point
{
	int _x;
	int _y;
	maze_point(int x, int y)
		:_x(x)
		, _y(y)
	{}
};

vector<maze_point> path_stack;//存儲每次周遊的路徑
vector<maze_point> min_costpath;//存儲最終的最優路徑

//列印vector中的路徑(vector每個元素是個坐标點maze_point)
void print_path(const vector<maze_point>& path)
{
	for (int i = 0; i < path.size(); i++)
	{
		cout << "[" << path[i]._x << "," << path[i]._y << "]";
		if (i < path.size() - 1)//每個坐标之間的間隔
		{
			cout << ",";
		}
	}
}

//主要的邏輯(尋找最優路徑)
//參數是坐标點，目前體力值

void search(int x, int y, int cur_p)
{
	//将目前坐标加入路徑，并且标記為已通路
	path_stack.push_back(maze_point(x, y));
	maze[x][y] = VISITED;

	//找到一條路徑了，但是不要急，和上一條的剩餘體力值比一比看哪一條更優
	if ((x == 0 && y == m - 1) && cur_p >= 0)
	{
		if (cur_p > final_p)//說明目前路徑更優
		{
			final_p = cur_p;
			min_costpath = path_stack;
		}

		//将目前結點彈出，即回退找下一條路徑
		path_stack.pop_back();
		maze[x][y] = 1;
		return;
	}

	//如果目前結點并非出口，則分别向左、右、上、下探索，
	//其中每個結點又當做一個節點探索其的左、右、上、下
	if (cur_p > 0)
	{
		for (int i = 0; i < 4; i++)
		{
			//更新移動後的坐标值
			int nx = x + dir[i][0];
			int ny = y + dir[i][1];

			//更新移動後的體力值
			int np = cur_p + cost[i];

			//如果更新後的坐标合法，并且該位置是1，即可走，則以該結點為主結點遞歸這個節點
			if (nx >= 0 && nx < n && ny >= 0 && ny < m && maze[nx][ny] == 1)
			{
				search(nx, ny, np);
			}
		}

		//來到這，說明該節點的四個方向都走不通，則該節點
		//不可能是路徑上的一個，則彈出該節點
		path_stack.pop_back();
		maze[x][y] = 1;
	}
}