|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
/**
|
|
|
* 功能：声明一个结构体，用来描述移动的横坐标与纵坐标
|
|
|
* 作者：黄海
|
|
|
* 时间：2019-11-17
|
|
|
*/
|
|
|
struct Node {
|
|
|
int x, y;
|
|
|
|
|
|
Node(int a, int b) {
|
|
|
x = a;
|
|
|
y = b;
|
|
|
}
|
|
|
};
|
|
|
|
|
|
//地图大小，一般大开一点方便存储
|
|
|
#define SIZE 100
|
|
|
|
|
|
//右
|
|
|
const int d[4][2] = {
|
|
|
{-1, 0},
|
|
|
{0, -1},
|
|
|
{1, 0},
|
|
|
{0, 1}};
|
|
|
|
|
|
//抽像后的地图，Flase：不可以走，True:可以走。
|
|
|
bool _map[SIZE][SIZE];
|
|
|
|
|
|
//考虑到要图形化输出，先存一份原图：
|
|
|
char pic[SIZE][SIZE];
|
|
|
|
|
|
//是不是访问过?
|
|
|
bool visit[SIZE][SIZE];
|
|
|
|
|
|
//本轮走的路径
|
|
|
vector<Node> path;
|
|
|
|
|
|
//全部路径，都记录下来
|
|
|
vector<vector<Node> > allpath;
|
|
|
|
|
|
//地图 m:行，n:列
|
|
|
int m, n;
|
|
|
|
|
|
//S:出发点,T:终点 ，那么sx,sy就是出发点的坐标，tx,ty就是终点的坐标
|
|
|
int sx, sy, tx, ty;
|
|
|
|
|
|
//深度优先搜索
|
|
|
void dfs(int x, int y) {
|
|
|
//如果找到了终点T，那么x=tx,y=ty
|
|
|
if (x == tx && y == ty) {
|
|
|
//记录这个结点
|
|
|
path.push_back(Node(x, y));
|
|
|
|
|
|
//将路径记录下来
|
|
|
allpath.push_back(path);
|
|
|
|
|
|
//退出准备下一次尝试,这次的任务不是找到就完事了，而是要把所有的可能都找到，然后对比找到最小和路径，所以，需要不停的回退！
|
|
|
path.pop_back();
|
|
|
return;
|
|
|
}
|
|
|
if (!_map[x][y]) return; //不能走就不走
|
|
|
if (visit[x][y]) return; //走过了也不走
|
|
|
|
|
|
//记录走过了这个结点(路径)
|
|
|
path.push_back(Node(x, y));
|
|
|
//标识走了这个结点
|
|
|
dfs(xx, yy);
|
|
|
}
|
|
|
visit[x][y] = 1;
|
|
|
//四个方向进行尝试
|
|
|
for (int i = 0; i < 4; ++i) {
|
|
|
int xx = x + d[i][0], yy = y + d[i][1];
|
|
|
//四个方向进行深度优先探索
|
|
|
//从纸箱中取回，表未没有走过
|
|
|
visit[x][y] = 0;
|
|
|
path.pop_back();
|
|
|
|
|
|
return;
|
|
|
}
|
|
|
|
|
|
/**
|
|
|
* 功能：输出路径
|
|
|
* 作者：黄海
|
|
|
* 时间：2019-11-17
|
|
|
* @param x
|
|
|
*/
|
|
|
void showpath(vector<Node> x) {
|
|
|
char s[SIZE][SIZE];
|
|
|
for (int i = 0; i < n; ++i) {
|
|
|
strcpy(s[i], pic[i]);
|
|
|
}
|
|
|
for (int i = 0; i < x.size(); ++i) {
|
|
|
s[x[i].x - 1][x[i].y - 1] = '+';
|
|
|
}
|
|
|
for (int i = 0; i < m; ++i) puts(s[i]);
|
|
|
printf("step = %d\n", x.size() - 1);
|
|
|
printf("\n");
|
|
|
}
|
|
|
|
|
|
//对比两种方案，如何算是优先级高，即数量少，步骤少。
|
|
|
bool cmp(vector<Node> x, vector<Node> y) {
|
|
|
return x.size() < y.size();
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
|
|
|
//读取m:行，n:列
|
|
|
scanf("%d %d", &m, &n);
|
|
|
|
|
|
//所谓初始值，就意味着下面的代码中需要在地图中找到S和T，然后修改sx,sy,tx,ty四个值。
|
|
|
//迷宫入口：
|
|
|
sx = 1; //初始值
|
|
|
sy = 1; //初始值
|
|
|
|
|
|
//迷宫出口：
|
|
|
tx = m; //初始值
|
|
|
ty = n; //初始值
|
|
|
|
|
|
//按行读取数据，共m行
|
|
|
for (int i = 0; i < m; i++) {
|
|
|
scanf("%s", pic[i]); //按行读入地图
|
|
|
char s[SIZE];
|
|
|
strcpy(s, pic[i]);//复制行地图数据到s中
|
|
|
|
|
|
//按列遍历
|
|
|
for (int j = 0; j < n; j++) {
|
|
|
//取出当前值
|
|
|
char c = s[j];
|
|
|
|
|
|
//开始点
|
|
|
if (c == 'S') {
|
|
|
sx = i + 1;
|
|
|
sy = j + 1;
|
|
|
_map[i + 1][j + 1] = true;
|
|
|
}//终点
|
|
|
else if (c == 'T') {
|
|
|
tx = i + 1;
|
|
|
ty = j + 1;
|
|
|
_map[i + 1][j + 1] = true;
|
|
|
}//不能走
|
|
|
else if (c == '#') {
|
|
|
_map[i + 1][j + 1] = false;
|
|
|
} else//可以走
|
|
|
{
|
|
|
_map[i + 1][j + 1] = true;
|
|
|
};
|
|
|
}
|
|
|
}
|
|
|
|
|
|
//深度优先，核心算法
|
|
|
dfs(sx, sy);
|
|
|
|
|
|
//如果没有找到方案
|
|
|
if (allpath.size() == 0) {
|
|
|
printf("没有适用的方案。\n");
|
|
|
} else {
|
|
|
//对数据进行排序，找出步骤最少的方案
|
|
|
sort(allpath.begin(), allpath.end(), cmp);
|
|
|
|
|
|
//输出最佳方案
|
|
|
printf("最佳方案:\n");
|
|
|
showpath(allpath[0]);
|
|
|
|
|
|
//输出其余方案
|
|
|
printf("其余方案:\n");
|
|
|
for (int i = 1; i < allpath.size(); ++i) {
|
|
|
showpath(allpath[i]);
|
|
|
}
|
|
|
//输出方案数
|
|
|
printf("方案数 = %d\n", allpath.size());
|
|
|
}
|
|
|
return 0;
|
|
|
}
|
|
|
/*
|
|
|
https://blog.csdn.net/szdytom/article/details/87537876
|
|
|
|
|
|
-- 下面是测试用例
|
|
|
5 6
|
|
|
....S#
|
|
|
.##...
|
|
|
.#..#.
|
|
|
#..##.
|
|
|
.T....
|
|
|
|
|
|
|
|
|
副另外两个样例：
|
|
|
4 4
|
|
|
S.##
|
|
|
..##
|
|
|
#..#
|
|
|
##.T
|
|
|
|
|
|
|
|
|
5 6
|
|
|
....S#
|
|
|
.##...
|
|
|
.#..#.
|
|
|
#..##.
|
|
|
.T....
|
|
|
|
|
|
*/
|
