CODE:拯救伟哥
题目 题目描述 Description 有一天，炜哥和欧能干一起去大魔王家里做（dao）客（luan），不巧被魔王发现了。魔王将炜哥和欧能干抓走了，关在了两个不同的房间里。魔王听说吃炜哥的肉可以长生不老（炜哥=唐僧？），于是开始准备晚饭。由于魔王疏忽，将一把钥匙漏在了欧能干的房间里。欧能干知道这个消息后，赶紧去拯救炜哥。炜哥生命危在旦夕，欧能干必须马上离开这个房间，救出炜哥。于是他找到了编程大牛的你。
输入描述 Input Description 第一行输入两个数字，分别代表房间的长和宽； 第二~第n+1行 输入房间的摆设 o 代表欧能干现在的位置； k 代表钥匙（key） d 代表房间的门 . 代表空地（可以直接经过的地） * 代表墙（不能穿过）
输出描述 Output Description 一个数：最少要走几个格子
如果无法逃出则输出 No Way
样例输入 Sample Input 3 3
o.k
d*.
…
样例输出 Sample Output 5
代码
#include<iostream>
#include<queue>
using namespace std;
int n,m;
const int maxn = 500;
int mp[maxn][maxn] = {0};
int ans = 0;
struct node{
int x,y;
int step;
};
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
int ok = 0;
void bfs(int startx,int starty,int flag)
{
int vis[maxn][maxn] = {0};
queue<node> q;
q.push((node){startx,starty,0});
vis[startx][starty] = 1;
node p;
while(!q.empty())
{
p = q.front();
q.pop();
if(flag==1&&mp[p.x][p.y]==2)
{
ans+=p.step;
return ;
}
if(flag==2&&mp[p.x][p.y]==3)
{
ans+=p.step;
cout << ans;
ok = 1;
return ;
}
for(int i = 0; i < 4; i++)
{
int x = p.x,y = p.y;
x+=dir[i][0];
y+=dir[i][1];
if(x>0&&x<=n&&y>0&&y<=m&&!vis[x][y]&&mp[x][y]!=0)
{
q.push((node){x,y,p.step+1});
vis[x][y] = 1;
}
}
}
return ;
}
int main()
{
cin >> m >> n;
int a,b,c,d;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <=m; j++)
{
char temp;
cin >> temp;
if(temp=='o')
{
a = i,b=j;
mp[i][j] = 1;
}
if(temp=='.')
mp[i][j] = 1;
if(temp=='*')
mp[i][j] = 0;
if(temp=='k')
{
c = i,d = j;
mp[i][j] = 2;
}
if(temp=='d')
{
mp[i][j] = 3;
}
}
}
bfs(a,b,1);
bfs(c,d,2);
if(!ok)
{
cout << "No Way" << endl;
}
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018年02月12日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读