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

· · 题解

01 迷宫的弱化版，BFS 版子题，哪要什么最短路……

唯一的区别就是没有墙了，改成只能走不同辐射区域。定义数组存辐射区能量正负极和安全区，所以要用整型变量。初始所有图内的点全部为真能走，走过的点不再重走置为假。所以只要这地方为真而且正负极与当前不同，即可入队。

如果下一步是目的地，直接返回值即可。

代码长这样：

#include<bits/stdc++.h>
using namespace std;
int n,sx,sy,ex,ey;
int f[105][105];
bool b[105][105];
struct wz{
    int x,y,ans;
};
queue<wz> q;
int gx[4]={1,-1,0,0};
int gy[4]={0,0,1,-1};
int bfs(){
    wz a;
    a.x=sx;
    a.y=sy;
    a.ans=0;
    q.push(a);
    b[sx][sy]=false;
    while(!q.empty()){
        a=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            wz xin;
            xin.x=a.x+gx[i];
            xin.y=a.y+gy[i];
            xin.ans=a.ans+1;
            if(xin.x==ex&&xin.y==ey) return xin.ans;
            if(b[xin.x][xin.y]&&f[xin.x][xin.y]!=f[a.x][a.y]) q.push(xin),b[xin.x][xin.y]=false;
        }
    }
    return -1;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            char c;
            cin>>c;
            if(c=='+') f[i][j]=1;
            if(c=='-') f[i][j]=-1;
            if(c=='A') sx=i,sy=j;
            if(c=='B') ex=i,ey=j;
            b[i][j]=true;
        }
    }
    cout<<bfs();
    return 0;
}