nyoj 逃离妖洞 1246（BFS）

小鱼儿 2024-02-17 19:04 46阅读 0赞

### 逃离妖洞 ###

时间限制： 1000 ms | 内存限制： 65535 KB

难度： 3

描述

唐僧不小心又掉入妖怪的迷宫了。这个迷宫有n行m列，共n\*m个方格。有的方格是空的，唐僧可以站在上面，有些是有障碍物的不能站。每次唐僧可以移动到相邻的8个空方格上。但是有些情况不能移动，即从两个方格的缝隙中移动，如图：![C678-1002-1.JPG][]

为了逃出妖怪的洞穴，唐僧需要触发悟空在某个方格留下的宝物，宝物都是留在空的方格中的。如果唐僧站在某个留有宝物的方格中，那么这个宝物就会被触发。为了逃离妖洞，唐僧务必按顺序依次触发K个宝物，当最后一个宝物被触发后，唐僧将会逃离妖洞。

现在唐僧已经知道这个迷宫中的障碍方格和有宝物的方格情况，开始唐僧站在一个给定的方格。问他是否可以逃离妖洞？

输入

一共有T（T<=20）组测试数据。  
  
每组含有行数n，列数m。（2<=n,m<=100）以及放有宝物的K（1<= K <=10）个方格。  
  
下面n行，每行包含m个字符，用'.'表示空的方格，用'\#'表示有障碍物的方格。  
  
下面一行是起点位置（x，y），保证是空的方格。  
下面的K行表示藏有宝物的空方格的位置，藏有宝物的方格是空的，没有障碍物。两个宝物不会放在同一个空方格中。需要按所给宝物顺序依次触发宝物。

输出

输出为了逃离妖洞，最少需要多少次移动。如果不能逃离，输出-1。

样例输入

3	
    3 3 2
    ...
    ...
    ...
    1 1
    1 3
    2 2
    3 3 1
    ...
    .#.
    ...
    1 1
    3 3
    2 3 1
    ..#
    .#.
    1 1
    2 3

样例输出

3
    3
     -1

需要注意两点：

1、宝物访问只能按照给定顺序访问。

2、唐僧站的初始位置可能是宝物，如果宝物不是第一个，则无法逃离。

#include<cstdio>
    #include<queue>
    #include<cstring> 
    using namespace std;
    const int maxn=100+5;
    struct node{
    	int x,y;
    	node(int x=0,int y=0):x(x),y(y){}
    }; 
    node ns; //初始位置 
    int n,m,k;
    char p[maxn][maxn]; 
    int d[maxn][maxn];  
    node t[10+2];  //储存k个结点（通过下标取得坐标） 
    int dir[][2]={
           {1,0},{0,1},{-1,0},{0,-1},{-1,-1},{1,1},{1,-1},{-1,1}};
    bool isValid(node nd){
    	return nd.x>0 && nd.x<=n && nd.y>0 && nd.y<=m;
    }
    int bfs(char ch){
        memset(d,0,sizeof(d));
    	queue<node> q;
    	q.push(ns);
    	while(!q.empty()){
    		node v=q.front();
    		q.pop();
    		if(p[v.x][v.y]==ch)return d[v.x][v.y];
            for(int i=0;i<8;i++)
    				{
                        int x=dir[i][0]+v.x,y=dir[i][1]+v.y; 
                        if(i>=4 && p[v.x][y]=='#' && p[x][v.y]=='#')continue;
                        if(p[x][y]>='a' && p[x][y]<='z' && ch<p[x][y])continue;    //如果是字母（代表宝物），判断是否该此时访问 
    					node u=node(x,y);	
    					if(isValid(u) && p[u.x][u.y]!='#' && !d[u.x][u.y]){
    						q.push(u);
    				        d[u.x][u.y]=d[v.x][v.y]+1;
    					}
    				}
    		 }
    	return -1;
    }
    int solve(){
    	if(p[ns.x][ns.y]>='a' && p[ns.x][ns.y]<='z' && p[ns.x][ns.y]>'a')return -1; //如果初始位置在宝物上并且不是第一个宝物 
    	int tatal=0;
    	for(int i=0;i<k;i++){
    		int temp=bfs(i+'a');
    		if(temp==-1)return -1;
    		tatal+=temp;
    		ns.x=t[i].x; //改变初始位置 
    		ns.y=t[i].y;
    	}
    	return tatal;
    }
    int main(){
    	int T;
    	scanf("%d",&T);
    	while(T--){
    		scanf("%d%d%d",&n,&m,&k);
    		getchar();
    		for(int i=1;i<=n;i++)
    			{
    			for(int j=1;j<=m;j++)scanf("%c",&p[i][j]); 
    			getchar();    //吃掉换行 
    			}
    		scanf("%d%d",&ns.x,&ns.y);
    		for(int i=0;i<k;i++){
    		int x,y; 
    			scanf("%d%d",&x,&y);
    		    p[x][y]=i+'a';   //将空格(.)用宝物（字母）表示 
    		    t[i]=node(x,y);
    		}	
    		printf("%d\n",solve());
    	}
    	return 0;
    }

[C678-1002-1.JPG]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/af5fe6f890804af9885b0aa8bea9f94d.png