#include "pch.h"
#include <iostream>
#include <stack>
using namespace std;
#if 0
const int RIGHT = 0;
const int DOWN = 1;
const int LEFT = 2;
const int UP = 3;
const int WAY_NUM = 4;
const int YES = 4;
const int NO = 5;
class Maze
{
public:
Maze(int row, int col)
:_row(row)
, _col(col)
{
_pMaze = new Node*[_row];
for (int i = 0; i < _row; ++i)
{
_pMaze[i] = new Node[_col];
}
}
void initNode(int x, int y, int val)
{
_pMaze[x][y]._x = x;
_pMaze[x][y]._y = y;
_pMaze[x][y]._val = val;
for (int i = 0; i < WAY_NUM; ++i)
{
_pMaze[x][y]._state[i] = NO;
}
}
void setNodeState()
{
for (int i = 0; i < _row; ++i)
{
for (int j = 0; j < _col; ++j)
{
if (_pMaze[i][j]._val == 1)
{
continue;
}
if (j < _col - 1 && _pMaze[i][j + 1]._val == 0)
{
_pMaze[i][j]._state[RIGHT] = YES;
}
if (i < _row - 1 && _pMaze[i + 1][j]._val == 0)
{
_pMaze[i][j]._state[DOWN] = YES;
}
if (j > 0 && _pMaze[i][j - 1]._val == 0)
{
_pMaze[i][j]._state[LEFT] = YES;
}
if (i > 0 && _pMaze[i - 1][j]._val == 0)
{
_pMaze[i][j]._state[UP] = YES;
}
}
}
}
void searchMazePath()
{
if (_pMaze[0][0]._val == 1)
{
return;
}
_stack.push(_pMaze[0][0]);
while (!_stack.empty())
{
Node top = _stack.top();
int x = top._x;
int y = top._y;
if (x == _row - 1 && y == _col - 1)
{
return;
}
if (_pMaze[x][y]._state[RIGHT] == YES)
{
_pMaze[x][y]._state[RIGHT] = NO;
_pMaze[x][y + 1]._state[LEFT] = NO;
_stack.push(_pMaze[x][y + 1]);
continue;
}
if (_pMaze[x][y]._state[DOWN] == YES)
{
_pMaze[x][y]._state[DOWN] = NO;
_pMaze[x + 1][y]._state[UP] = NO;
_stack.push(_pMaze[x + 1][y]);
continue;
}
if (_pMaze[x][y]._state[LEFT] == YES)
{
_pMaze[x][y]._state[LEFT] = NO;
_pMaze[x][y - 1]._state[RIGHT] = NO;
_stack.push(_pMaze[x][y - 1]);
continue;
}
if (_pMaze[x][y]._state[UP] == YES)
{
_pMaze[x][y]._state[UP] = NO;
_pMaze[x - 1][y]._state[DOWN] = NO;
_stack.push(_pMaze[x - 1][y]);
continue;
}
_stack.pop();
}
}
void showMazePath()
{
if (_stack.empty())
{
cout << "不存在一条迷宫路径!" << endl;
}
else
{
while (!_stack.empty())
{
Node top = _stack.top();
_pMaze[top._x][top._y]._val = '*';
_stack.pop();
}
for (int i = 0; i < _row; ++i)
{
for (int j = 0; j < _col; ++j)
{
if (_pMaze[i][j]._val == '*')
{
cout << "* ";
}
else
{
cout << _pMaze[i][j]._val << " ";
}
}
cout << endl;
}
}
}
private:
struct Node
{
int _x;
int _y;
int _val;
int _state[WAY_NUM];
};
Node **_pMaze;
int _row;
int _col;
stack<Node> _stack;
};
int main()
{
cout << "请输入迷宫的行列数(例如:10 10):";
int row, col, data;
cin >> row >> col;
Maze maze(row, col);
cout << "请输入迷宫的路径信息(0表示可以走,1表示不能走):" << endl;
for (int i = 0; i < row; ++i)
{
for (int j = 0; j < col; ++j)
{
cin >> data;
maze.initNode(i, j, data);
}
}
maze.setNodeState();
maze.searchMazePath();
maze.showMazePath();
return 0;
}
#endif