7-5 最近距离 (25 分)

亦凉 2023-10-08 09:56 36阅读 0赞

7-5 最近距离 (25 分)

在一个游戏中，玩家处于一个如下所示12行12列的迷宫：

0,1,0,0,0,1,1,1,0,1,0,1

0,0,0,1,0,0,0,0,1,0,0,1

0,1,0,1,0,1,1,1,0,1,0,0

0,1,0,0,0,0,0,1,0,0,1,1

0,0,0,0,1,0,0,0,0,0,0,0

0,0,1,0,0,0,1,0,0,0,1,0

0,0,1,0,0,0,0,0,1,0,0,0

1,0,0,1,0,1,0,0,0,1,0,1

0,0,1,0,1,0,1,0,1,0,0,0

0,0,0,0,0,1,0,0,0,1,1,0

0,0,0,0,0,1,0,0,0,0,0,0

0,1,0,1,0,0,0,1,0,1,0,0

其中迷宫由0,1组成，0表示道路，1表示障碍物。

现在要根据玩家和游戏中被攻击的虚拟boss所在位置，给玩家以最近距离的提示。

最近距离：即玩家走到boss所走的最少步数。（注：路线中的一步是指从一个坐标点走到其上下左右相邻坐标点。）  
输入格式:

输入4个整数a,b,c,d（即玩家和虚拟boss在迷宫中的坐标位置分别为(a,b) 、(c,d)）， 其中 0<=a,b,c,d<12。  
输出格式:

输出在迷宫中从(a,b)出发到达(c,d)的最少步数，如果(a,b)永远无法到达(c,d)则输出10000。  
输入样例:

在这里给出一组输入。例如：

0 0 11 11

输出样例:

在这里给出相应的输出。例如：

#include <stdio.h>
    int map[12][12] = {
         0,1,0,0,0,1,1,1,0,1,0,1,
    
    					0,0,0,1,0,0,0,0,1,0,0,1,
    					
    					0,1,0,1,0,1,1,1,0,1,0,0,
    					
    					0,1,0,0,0,0,0,1,0,0,1,1,
    					
    					0,0,0,0,1,0,0,0,0,0,0,0,
    					
    					0,0,1,0,0,0,1,0,0,0,1,0,
    					
    					0,0,1,0,0,0,0,0,1,0,0,0,
    					
    					1,0,0,1,0,1,0,0,0,1,0,1,
    					
    					0,0,1,0,1,0,1,0,1,0,0,0,
    					
    					0,0,0,0,0,1,0,0,0,1,1,0,
    					
    					0,0,0,0,0,1,0,0,0,0,0,0,
    					
    					0,1,0,1,0,0,0,1,0,1,0,0};//初始地图 
    int c, d, count, min = 10000;
    int A[4] = {
        -1, 1, 0, 0};//a的方向 
    int B[4] = {
        0, 0, -1, 1};//b的方向 
    void dfs(int a, int b)
    {
        
    	if (a == c && b == d)//走到终点就输出 
    	{
        
    		if (count < min)
    		{
        
    			min = count;
    		}
    	}
    	else
    	{
        
    		for (int i = 0; i < 4; i++)
    		{
        
    			if (a + A[i] >= 0 && a + A[i] < 12 && b + B[i] >= 0 && b + B[i] < 12
    			&& !map[a + A[i]][b + B[i]] && count < min)//剪枝 
    			{
        
    				map[a + A[i]][b + B[i]] = 1;
    				count++;
    				dfs(a + A[i], b + B[i]);
    				count--;
    				map[a + A[i]][b + B[i]] = 0;
    			}
    		}
    	}
    }
    int main()
    {
        
    	int a, b;
    	scanf("%d%d%d%d", &a, &b, &c, &d);
    	dfs(a, b);
    	printf("%d", min);
    	return 0;
    }