迷宫选路[递归和递推]

后面想了想 还是不要取1 0取 4和3比较好
这样些比书上感觉好理解些，而且可以找出所有路径

#include<iostream>
#include<vector>
using namespace std;
int m, n; //终点坐标

struct node
{
	int x, y;
};
vector<node>s;
int map[5][3];
int mark[5][3];
node Node[8] = { {-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1} };
void seekPath(int x, int y)
{
	int xx, yy;
	if (x == m && y == n)
	{
		for (auto it : s)
		{
			cout << "("<<it.x << "," << it.y<<")" << "->";
		}
		cout << endl;
		return;
	}
	for (int i = 0; i < 8; i++)
	{
		xx = x + Node[i].x, yy = y + Node[i].y;
		if (!map[xx][yy] && !mark[xx][yy])
		{
			mark[xx][yy] = 1;
			s.push_back(node{ xx,yy });
			seekPath(xx, yy);
			mark[xx][yy] = 0;
			s.pop_back();
		}
	}
}
int main()
{
	cin >> m >> n;
	for (int i = 0; i < 5; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			cin >> map[i][j];
			mark[i][j] = 0;
		}
	}
	mark[1][0] = 1;
	s.push_back(node{ 1,0 });
	seekPath(1, 0);
}

#include<iostream>
using namespace std;
int m, n; //终点坐标
struct node
{
	int x, y;
};
int map[5][3];
int mark[5][3];
node Node[8] = { {-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
bool seekPath(int x, int y)
{
	int xx, yy;
	if (x == m && y == n)
		return true;
	for (int i = 0; i < 8; i++)
	{
		xx = x + Node[i].x, yy = y + Node[i].y;
		if (!map[xx][yy] && !mark[xx][yy])
		{
			mark[xx][yy] = 1;
			if (seekPath(xx, yy))
			{
				cout << "(" << xx << "," << yy << ")" << "->";
				return true;
			}
		}
	}
}
int main()
{
	cin >> m >> n;
	for (int i = 0; i < 5; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			cin >> map[i][j];
			mark[i][j] = 0;
		}
	}
	mark[1][0] = 1;
	if (seekPath(1, 0))
		cout << "(1,0)";
}

栈 递推

#include<iostream>
#include<stack>
using namespace std;
int m, n;
struct node
{
	int x, y;
};
int map[5][3];
int mark[5][3];
node Node[8] = { {-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1} };
void path()
{
	int i, j, xx, yy, d;
	mark[1][0] = 4;
	stack<node>s;
	node st;
	st.x = 1, st.y = 0;
	s.push(st);
	while (!s.empty())
	{
		i = s.top().x, j = s.top().y, d = 0;
		while (d < 8)
		{
			xx = i + Node[d].x;
			yy = j + Node[d].y;
			if (xx == m && yy == n)
			{
				cout << m << "," << n << "->";
				while (!s.empty())
				{
					cout << s.top().x << "," << s.top().y << "->";
					s.pop();
				}
				return;
			}
			if (map[xx][yy]==3 && mark[xx][yy]==3)
			{
				mark[xx][yy] = 4;
				node temp; temp.x = xx, temp.y = yy;
				s.push(temp);
				i = xx, j = yy;
				d = 0;
			}
			else
			{
				d++;
			}
		}
	}
	
}
int main()
{
	cin >> m >> n;
	for (int i = 0; i < 5; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			cin >> map[i][j];
			mark[i][j] = 3;
		}
	}
	path();
}