2843 拯救炜哥（bfs）

阳光穿透心脏的1/2处 2022-06-18 09:21 127阅读 0赞

题目描述 Description

有一天，炜哥和欧能干一起去大魔王家里做（dao）客（luan），不巧被魔王发现了。魔王将炜哥和欧能干抓走了，关在了两个不同的房间里。魔王听说吃炜哥的肉可以长生不老（炜哥=唐僧？），于是开始准备晚饭。由于魔王疏忽，将一把钥匙漏在了欧能干的房间里。欧能干知道这个消息后，赶紧去拯救炜哥。炜哥生命危在旦夕，欧能干必须马上离开这个房间，救出炜哥。于是他找到了编程大牛的你。

输入描述 Input Description

第一行输入两个数字，分别代表房间的长和宽；  
第二~第n+1行 输入房间的摆设  
o 代表欧能干现在的位置；  
k 代表钥匙（key）  
d 代表房间的门  
. 代表空地（可以直接经过的地）  
\* 代表墙（不能穿过）

输出描述 Output Description

一个数：最少要走几个格子

如果无法逃出则输出  No Way

样例输入 Sample Input

3 3

o.k

d\*.

...

样例输出 Sample Output

数据范围及提示 Data Size & Hint

1<=n,m<=1000

原创：二中苏元实验学校 欧宁

思路：先去拿钥匙，在从拿钥匙的地方走到门，求两次的步数之和

#include<cstdio>
    #include<iostream>
    #include <string.h>
    #include<queue>
    using namespace std; 
    int n,m;
    char map[1010][1010];
    int dir[4][2] = {-1,0,0,-1,0,1,1,0};
    int v[1010][1010]={0};
    struct st 
    {
    	int x,y,c;
    };
    queue<struct st> Q;
    int bfs(st s,st e)
    {
    	st temp;
    	int i,j,k;
    	memset(v,0,sizeof(v));
    	v[s.x][s.y] = 1;
    	s.c = 0;
    	Q.push(s);
    	while (!Q.empty())
    	{
    		s = Q.front();
    		Q.pop();
    		if (s.x == e.x && s.y == e.y)
    		{
    			return s.c;
    		}
    		for (i=0; i<4; i++)
    		{
    			temp.x = dir[i][0] + s.x;
    			temp.y = dir[i][1] + s.y;
    			if (temp.x>=0 && temp.y>=0 && temp.x<n &&temp.y<m && map[temp.x][temp.y] != '*' && !v[temp.x][temp.y])
    			{
    				v[temp.x][temp.y] = 1;
    				temp.c = s.c+1;
    				Q.push(temp);
    			}
    		}
    	}
    	return -1;
    }
    int main()
    {
    	st od,kd,dd;
    	int i,j,num,num2;
    	cin>>n>>m;
    	getchar();
    	for (i=0; i<n; i++)
    	{
    		cin>>map[i];
    	}
    	for (i=0; i<n; i++)
    	{
    		for (j=0; j<m; j++)
    		{
    			if (map[i][j] == 'o')
    			{
    				od.x = i; od.y = j;
    			}
    			else if (map[i][j] == 'k')
    			{
    				kd.x = i; kd.y = j;
    			}
    			else if (map[i][j] == 'd')
    			{
    				dd.x = i; dd.y = j;
    			}
    		}
    	}
    	num = bfs(od,kd);
    	if ( num == -1 )
    	{
    		cout<<"No Way";
    		return 0;
    	}
    	num2 = bfs(kd,dd);
    	if (num2 == -1)
    	{
    		cout<<"No Way";
    		return 0;
    	}
    	cout<<num+num2;//最终步数就是拿钥匙的步数和从拿钥匙的 地方到门的步数之和 
    	return 0;
    }