蓝桥穿越雷区

灰太狼 2022-06-18 07:51 173阅读 0赞

X星的坦克战车很奇怪，它必须交替地穿越正能量辐射区和负能量辐射区才能保持正常运转，否则将报废。  
某坦克需要从A区到B区去（A，B区本身是安全区，没有正能量或负能量特征），怎样走才能路径最短？

已知的地图是一个方阵，上面用字母标出了A，B区，其它区都标了正号或负号分别表示正负能量辐射区。  
例如：  
A + – + –  
– + – – +  
– + + + –  
\+ – + – +  
B + – + –

坦克车只能水平或垂直方向上移动到相邻的区。

数据格式要求：

输入第一行是一个整数n，表示方阵的大小， 4<=n<100  
接下来是n行，每行有n个数据，可能是A，B，+，-中的某一个，中间用空格分开。  
A，B都只出现一次。

要求输出一个整数，表示坦克从A区到B区的最少移动步数。  
如果没有方案，则输出-1

例如：  
用户输入：  
5  
A + – + –  
– + – – +  
– + + + –  
\+ – + – +  
B + – + –

则程序应该输出：

思路：bfs 判断当前符号和上次的符号是否不同即可

——写了好几偏宽搜了 还是不长记性

#include<iostream>
    #include<queue>
    using namespace std;
    struct st
    {
    	int x,y,c;
    };
    int n,dir[4][2]={-1,0,1,0,0,-1,0,1};
    char map[110][110];
    int v[110][110]={0};
    queue<struct st> Q;
    int bfs(struct st s, struct st e)
    {
    	int xx,yy,i,j;
    	s.c=0;
    	Q.push(s);
    	v[s.x][s.y] = 1;
    	while (!Q.empty())
    	{
    		struct st t;
    		t = Q.front();
    		Q.pop();
    		if (t.x == e.x && t.y == e.y)
    		{
    			return t.c;
    		}
    		for (i=0; i<4; i++)
    		{
    			xx = dir[i][0] + t.x;
    			yy = dir[i][1] + t.y;
    			if (xx<0||yy<0||xx>=n||yy>=n||v[xx][yy]||(map[t.x][t.y]==map[xx][yy]))//不满足的条件 
    			{
    				continue;
    			}
    			struct st temp;
    			temp.x = xx;
    			temp.y = yy;
    			temp.c = t.c+1;
    			v[xx][yy] = 1;
    			Q.push(temp);
    		}
    	}
    	return -1;
    }
    int main()
    {
    	int i,j;
    	struct st s,e;
    	cin>>n;
    	for (i=0; i<n; i++)
    	{
    		for (j=0; j<n; j++)
    		{
    			cin>>map[i][j];
    			if (map[i][j] == 'A')
    			{
    				s.x = i;
    				s.y = j;
    			}
    			if (map[i][j] == 'B')
    			{
    				e.x = i;
    				e.y = j;
    			}
    		}
    	}
    	cout<<bfs(s,e);
    	return 0;
    }