洛谷 P8628 [蓝桥杯 2015 国 AC] 穿越雷区

[蓝桥杯 2015 国 AC] 穿越雷区

题目链接

https://www.luogu.com.cn/problem/P8628#submit

题目描述

$X$ 星的坦克战车很奇怪，它必须交替地穿越正能量辐射区和负能量辐射区才能保持正常运转，否则将报废。

某坦克需要从 $A$ 区到 $B$ 区去（$A$，$B$ 区本身是安全区，没有正能量或负能量特征），怎样走才能路径最短？

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

例如：

A + - + -
- + - - +
- + + + -
+ - + - +
B + - + -

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

输入格式

输入第一行是一个整数 $n$，表示方阵的大小，$4\le n<100$。

接下来是 $n$ 行，每行有 $n$ 个数据，可能是 A，B，+，- 中的某一个，中间用空格分开。

输出格式

要求输出一个整数，表示坦克从 $A$ 区到 $B$ 区的最少移动步数。

如果没有方案，则输出 $-1$。

样例 #1

样例输入 #1

5
A + - + -
- + - - +
- + + + -
+ - + - +
B + - + -

样例输出 #1

10

提示

时限 1 秒, 512M。蓝桥杯 2015 年第六届国赛

思路解析

有条件限制的最短路，只能走到与自己符号不同的地方。
唯一需要注意的就是读入。不过 $Cpp$ 有神器：cin，直接无脑读即可。但是用getchar()需要注意换行符，scanf()需要注意空格。

CODE

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#define ll long long
#define INF 0x3f3f3f3f 

using namespace std;

typedef pair<int, int> pii;

const int N = 110;
char g[N][N]; // 定义一个二维字符数组，用来存储地图
int n; // 定义一个整数变量，用来存储地图的大小
int dist[N][N]; // 定义一个二维整数数组，用来存储每个位置到A点的最短距离
bool st[N][N]; // 定义一个二维布尔数组，用来标记每个位置是否已经入队
int newx[4] = {
   -1, 0, 1, 0}; // 定义一个一维整数数组，用来存储四个方向的横坐标变化
int newy[4] = {
   0, 1, 0, -1}; // 定义一个一维整数数组，用来存储四个方向的纵坐标变化
int ax, ay, bx, by; // 定义四个整数变量，用来存储A点和B点的坐标

void spfa(){
    // 定义一个函数，用来实现SPFA算法，求出每个位置到A点的最短距离
    memset(dist, INF, sizeof dist); // 初始化dist数组
    dist[ax][ay] = 0; // 将A点的距离设为0
    
    queue<pii> q; 		// 定义一个队列，用来存储待更新的位置
    q.push({
   ax, ay}); 	// 将A点入队
    st[ax][ay] = true; 	// 将A点标记为已入队
    
    while(q.size()){
    	// 当队列不为空时，循环执行以下操作
        auto t = q.front(); 	// 取出队首元素
        q.pop(); 		// 将队首元素出队
        
        int x = t.first, y = t.second; 	// 获取队首元素的坐标
        st[x][y] = false; 	// 将队首元素标记为未入队
        
        for(int i = 0; i < 4; ++i){
    // 遍历四个方向
            int nex = x + newx[i]; 	// 计算下一个位置的横坐标
            int ney = y + newy[i]; 	// 计算下一个位置的纵坐标
            
            // 判断下一个位置是否在地图范围内
            if(nex >= 1 && nex <= n && ney >= 1 && ney <= n){
    
            	// 判断下一个位置的符号是否和当前位置不同
                if(g[x][y] != g[nex][ney]){
    
                	// 判断是否可以用当前位置更新下一个位置的距离
                    if(dist[nex][ney] > dist[x][y] + 1){
    
                        dist[nex][ney] = dist[x][y] + 1; // 更新下一个位置的距离
                        
                        if(!st[nex][ney]){
    // 判断下一个位置是否已经入队
                            st[nex][ney] = true; // 将下一个位置标记为已入队
                            q.push({
   nex, ney}); // 将下一个位置入队
                        }
                    }
                }
            }
        }
    }
}

int main(){
   
    cin >> n; // 输入地图的大小
    
    for(int i = 1; i <= n; ++i){
   
        for(int j = 1; j <= n; ++j){
   
            char s;
            cin >> s; 	// 输入每个位置的字符
            
            if(s == 'A'){
    	// 如果是A，记录A点的坐标
                ax = i;
                ay = j;
            }else if(s == 'B'){
    // 如果是B，记录B点的坐标
                bx = i;
                by = j;
            }else{
    	// 否则，将字符存入地图数组
                g[i][j] = s;
            }
        }
    }
    
    spfa(); // 调用spfa函数，求出每个位置到A点的最短距离
    
    // 如果B点的距离是无穷大，说明无法到达，输出-1
    // 否则，输出B点的距离
    if(dist[bx][by] == INF) printf("%d\n", -1); 
    else printf("%d\n", dist[bx][by]); 
}

这题应该还能用bfs/dfs过掉，之后再来看看。