// CatDFS.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<Windows.h>
#include<map>

using namespace std;

//6行6列地图
const int Row = 6;
const int Col = 6;

//将Q版地图用二维数组进行标定，0代表畅通无阻，1代表路障，-1代表深水坑
int Qmap[Row][Col] = { 0,0,0,0,1,0,
				 0,0,-1,-1,0,0,
				 0,1,0,0,0,0,
				 0,0,0,-1,0,0,
				 0,0,0,1,0,0,
				 0,0,0,0,0,0 };

//这是一个和map相同容积的标记数组，作用是标记羊羹君已经走过的坐标，避免重复行走
//因为假设我们不使用一个额外的数组储存羊羹君的行走历史记录，那么可能会存在重复行走的死循环
int tag[Row][Col] = { 0 };


//记录羊羹君走过的坐标，使用索引：坐标 map记录
class Coord
{
public:
	Coord() {};
	Coord(int i, int j) :x(i), y(j) {};
	~Coord() {};
	int x;
	int y;

};
map<int, Coord> pathMap;
int pathIndex = 0;	

//记录线路步数
int totalStep = 0;

//羊羹君的移动方式，也就是“碰壁式移动”，先右走，再下走，再左走，在上走
//相应的坐标计算规则则是如下
int nextMove[4][2] = { {0,1},		//坐标右移
					{1,0},		//坐标下移
					{0,-1},		//坐标左移
					{-1,0} };	//坐标上移

//深度优先搜索算法
//因为羊羹君每走一步，都会环顾四周，观察下一步可以走哪里，所以可以递归进行
//参数首先确认当前走到了二维数组的哪个位置，也就是xy
//参数同时确认当前已经走了多少步了，方便我们找到最短路线
void Dfs(int x, int y, int step)
{
	//当我们到达[5,5]坐标时，代表我们已经找到小鱼干了
	//这是我们就打印出来羊羹君走了多少步
	//同时将羊羹君每次行走的坐标示意图也打印出来
	if (x == (Row - 1) && y == (Col - 1))
	{
		//记录最短路线步数
		if (totalStep < step)
		{
			totalStep = step;
		}
		printf("conguratulation 羊羹君 find the fish totalStep = %d\n", totalStep);
		for (int i = 0; i < Row; i++)
		{
			for (int j = 0; j < Col; j++)
			{
				printf("%d ", tag[i][j]);
			}
			printf("\n");
		}
		for (map<int, Coord>::iterator it = pathMap.begin(); it != pathMap.end(); it++)
		{
			printf("index = %d x=%d y=%d\n", it->first, it->second.x, it->second.y);
		}
		return;
	}
	int tx, ty;
	for (int i = 0; i < 3; i++)
	{
		//tx，ty表示下一步的二维坐标值
		tx = x + nextMove[i][0];
		ty = y + nextMove[i][1];
		//如果下一步坐标越界了，就直接跳过
		if (tx < 0 || tx >= Row || ty < 0 || ty >= Col)
		{
			continue;
		}
		//如果下一步坐标在地图map中标记为0通畅，同时tag标记数组表示这个坐标没有走过
		//那么我们就表示这一步行走正确，同时进行递归DFS
		if (Qmap[tx][ty] == 0 && tag[tx][ty] == 0)
		{
			tag[tx][ty] = 1;			//先标记tag数组，表示这个坐标已经行走过了，避免重复
			pathMap[pathIndex] = Coord(tx, ty);  //记录坐标map
			++pathIndex;
			Dfs(tx, ty, step + 1);		//然后进行DFS递归
			//如果DFS递归失败（没找到小鱼干，且这条路走堵死了）
			//那么回滚tag数组标记这个坐标没有行走过，并且清理路线中的坐标
			//同时继续for循环进行下一个方向的探索
			tag[tx][ty] = 0;	
			--pathIndex;
			pathMap.erase(pathIndex);
		}
	}
}


int main()
{
	for (int i = 0; i < Row; i++)
	{
		for (int j = 0; j < Col; j++)
		{
			printf("%d ", Qmap[i][j]);
		}
		printf("\n");
	}
	tag[0][0] = 1;
	pathMap[pathIndex] = Coord(0, 0);
	++pathIndex;
	Dfs(0, 0, 0);
    return 0;
}