电路布线或迷宫问题最短路径（广度优先搜索）
2019-05-30 本文已影响0人
步行植物
第一次用递归，可以算出来，但是内存超限了。第二次用了最短路径，成了。
题目：
题目描述
小明置身于一个迷宫，请你帮小明找出从起点到终点的最短路程。
小明只能向上下左右四个方向移动。
输入
输入包含多组测试数据。输入的第一行是一个整数T，表示有T组测试数据。
每组输入的第一行是两个整数N和M（1<=N,M<=100）。
接下来N行，每行输入M个字符，每个字符表示迷宫中的一个小方格。
字符的含义如下：
‘S’：起点
‘E’：终点
‘-’：空地，可以通过
‘#’：障碍，无法通过
输入数据保证有且仅有一个起点和终点。
输出
对于每组输入，输出从起点到终点的最短路程，如果不存在从起点到终点的路，则输出-1。
递归法：
样例输入
1
5 5
S-###
-----
##---
E#---
---##
样例输出
9
代码：
#include <iostream> //注意，这个程序是n行m列，和我们平常的nm的含义不一样
#include<vector>
#include<queue>
using namespace std;
priority_queue<int, vector<int>, greater<int> > q; //存路径
void visit( vector< vector<int> > cell,int i,int j,int endi,int endj,int n,int m) //找路径
{
if(i==endi&&j==endj)
{
int all=0;
for(int nn=0;nn<n;nn++)
for(int mm=0;mm<m;mm++)
if(cell[nn][mm]==1)
all++;
q.push(all);
}
cell[i][j]=1; //走过的设为1
if(j-1>=0&&cell[i][j-1]==0)
visit(cell,i,j-1,endi,endj,n,m);
if(j+1<m&&cell[i][j+1]==0)
visit(cell,i,j+1,endi,endj,n,m);
if(i-1>=0&&cell[i-1][j]==0)
visit(cell,i-1,j,endi,endj,n,m);
if(i+1<n&&cell[i+1][j]==0)
visit(cell,i+1,j,endi,endj,n,m);
cell[i][j]=0; //都不行就设置成0
}
int main()
{
int times;
cin>>times; //表示有times组测试数据
int m,n;
int starti=0,startj=0,endi=0,endj=0; //起点和终点
char current;
for(int i=0;i<times;i++)
{
cin>>n; //n行
cin>>m; //m列
vector< vector<int> > cell(n, vector<int>(m));
for(int nn=0;nn<n;nn++) //录入迷宫
for(int mm=0;mm<m;mm++)
{
cin>>current;
if(current=='S')
{
starti=nn;
startj=mm;
cell[nn][mm]=0;
}
if(current=='E')
{
endi=nn;
endj=mm;
cell[nn][mm]=0;
}
if(current=='-')
cell[nn][mm]=0; //表示可以走
if(current=='#')
cell[nn][mm]=2; //表示围墙
}
visit(cell,starti,startj,endi,endj,n,m);
if(q.size()==0)
cout<<-1;
if(q.size()!=0)
cout<<q.top();
while(!q.empty())
q.pop();
}
return 0;
}
最短路径（非递归）：
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int starti , startj , endi , endj ; //起点和终点
struct Position //记录四个移动方向
{
int row;
int col;
Position(int x,int y):row(x),col(y){}
};
vector< vector<int> >Input(int n,int m)
{
vector< vector<int> > cell(n + 2, vector<int>(m + 2)); //n+2行,m+2列
char current;
for (int nn = 0; nn < n + 2; nn++) //录入迷宫
for (int mm = 0; mm < m + 2; mm++)
{
if (nn == 0 || mm == 0 || nn == n + 1 || mm == m + 1)
{
cell[nn][mm] = 2; //最外面一圈用2围起来
continue;
}
cin >> current; //把迷宫转化为数字矩阵
if (current == 'S')
{
starti = nn;
startj = mm;
cell[nn][mm] = 2; //初始的位置不能再走了
}
if (current == 'E')
{
endi = nn;
endj = mm;
cell[nn][mm] = 0;
}
if (current == '-')
cell[nn][mm] = 0; //表示可以走
if (current == '#')
cell[nn][mm] = 2; //表示围墙
}
return cell;
}
/*寻找路径，若找到返回长度，没有路径返回-1*/
int FindPath(vector< vector<int> > cell)
{
Position offsets[4] = { {0,1},{1,0},{0,-1},{-1,0} };
Position here(starti,startj),nbr(0,0);
queue<Position>Q;
while(1)
{
for(int i=0;i<4;i++)
{
nbr.row=here.row+offsets[i].row;
nbr.col=here.col+offsets[i].col;
if (cell[nbr.row][nbr.col] == 0)
{
cell[nbr.row][nbr.col] = cell[here.row][here.col] + 1;
Q.push(nbr); //能走才存，不能走不存
}
if(nbr.row==endi&&nbr.col==endj)
break;
}
if(nbr.row==endi&&nbr.col==endj)
break;
if(Q.empty())
return -1;
here=Q.front();
Q.pop();
}
return cell[nbr.row][nbr.col]-2; //最开始把起点步数设成2 了
}
int main()
{
int times;
cin >> times; //表示有times组测试数据
int m, n;
for (int i = 0; i < times; i++)
{
cin >> n; //n行
cin >> m; //m列
vector< vector<int> > cell=Input(n, m);
cout<<FindPath(cell)<<endl;
}
return 0;
}
BFS
#define Question5
#ifdef Question5
#define UnDebug
#ifdef Debug
#include <ctime>
#endif
#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
using namespace std;
typedef pair<int, int> P; //存储移动
const int Max = 100; //最大有Max行或者列
const int INF = -1;
char Map[Max + 10][Max + 10];
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}; //4组方向
int diction[Max + 10][Max + 10]; //记录已走步数
int sx, sy, ex, ey; //起始坐标sx，sy；出口坐标ex，ey
void InputMap(int N, int M); //录入迷宫
void OutputMap(int N, int M); //输出路径
void BFS(int N, int M); //广度优先算法
int main()
{
#ifdef Debug
freopen("in.txt", "r", stdin);
clock_t start, finish;
double totaltime;
start = clock();
#endif
int T, N, M;
cin >> T;
while (T--)
{
cin >> N >> M;
InputMap(N, M); //录入迷宫，N行，每行输入M个字符
BFS(N, M); ////广度优先算法
cout << diction[ey][ex] << endl;
}
#ifdef Debug
finish = clock();
totaltime = (double)(finish - start) / CLOCKS_PER_SEC;
cout << "Times : " << totaltime * 1000 << "ms" << endl;
system("pause");
#endif
return 0;
}
void InputMap(int N, int M) //录入迷宫，N行，每行输入M个字符
{
bool sok = 1; //起始坐标没有录入
bool eok = 1; //出口坐标没有录入
for (int i = 0; i < N; i++)
{
cin >> Map[i]; //录入第i行
for (int j = 0; j < M; j++)
{
if (sok && Map[i][j] == 'S')
{
sx = j; //起始坐标x
sy = i; //起始坐标y
sok = 0;
}
if (eok && Map[i][j] == 'E')
{
ex = j; //出口坐标ex，ey
ey = i;
eok = 0;
}
}
}
}
void OutputMap(int N, int M)
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
cout << Map[i][j] << " ";
}
cout << endl;
}
}
void BFS(int N, int M) //广度优先算法
{
queue<P> que;
memset(diction, INF, sizeof(diction)); //diction数组全部置为-1
que.push(P(sy, sx)); //放入开始结点坐标，记录走过的路
diction[sy][sx] = 0; //开始坐标已走步数记为0
while (!que.empty()) //当队列中还记有走过的路
{
P curPoint = que.front(); //取首元素
que.pop(); //弹出首元素（留到后面再判断）
for (int i = 0; i < 4; i++) //四个方向依次尝试
{
int newx = curPoint.second + dx[i]; //记录下当前操作后位置
int newy = curPoint.first + dy[i]; //记录下当前操作后位置
if (newy >= 0 && newy < N && //如果移动没有超出边界
newx >= 0 && newx < M &&
Map[newy][newx] != '#' && //如果移动到不是#的位置
diction[newy][newx] == INF) //如果这个位置还没有走过
{
que.push(P(newy, newx)); //将这个移动放入队列
diction[newy][newx] = diction[curPoint.first][curPoint.second] + 1;
//标记走过这个位置，并且记录下已经走的步数
if (newx == ex && newy == ey) //如果找到出口
return;
}
}
}
}
#endif
