题目描述
给定n*m的迷宫 (2<n,m<24) ,迷宫中'0'代表路,'1'代表墙,'2'代表起点,'3'代表终点,求起点到终点最短距离
输入
多实例测试 第一行输入n,m 下面是n行,每行输入m个字符
输出
输出起点到终点最短距离
样例输入
5 3
0 0 0
0 1 0
0 2 0
0 1 3
0 0 0
样例输出
2
代码：
//#include<bits/stdc++.h> 万能头文件
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
char ma[205][205];
int dir[][2] = { 1,0,-1,0,0,1,0,-1 };
int n, m;
struct ff
{
int x, y, time;
friend bool operator<(ff n1, ff n2)
{
return n2.time < n1.time;
}
} p, s, t;
void bfs(int a, int b)
{
priority_queue<ff>q;
p.x = a, p.y = b, p.time = 0;
q.push(p);
while (!q.empty())
{
s = q.top();
q.pop();
for (int i = 0; i < 4; i++)
{
t.x = s.x + dir[i][0];
t.y = s.y + dir[i][1];
if (t.x >= 0 && t.x < n&&t.y >= 0 && t.y < m&&ma[t.x][t.y]!='1')
{
if (ma[t.x][t.y] == '3')
{
printf("%d\n", s.time + 1);
return;
}
if (ma[t.x][t.y] == '0')
{
t.time = s.time + 1;
}
q.push(t);
ma[t.x][t.y] = '1';
}
}
}
}
int main()
{
int xx, yy;
while (~scanf("%d%d", &n, &m))
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> ma[i][j];
if (ma[i][j] == '2')
{
xx = i;
yy = j;
}
}
}
bfs(xx, yy);
}
}
