ACM考核题中的BFS样题

前言：

果然功夫不负有心人，在前几天的第一次考核中我拿到了榜一，只不过可惜的是我没有ak，而那道我没有写出来的题就是我下面要展示的。

签到题——爆发式

Description

因为媛泽一个小女生独自出国父母不放心，媛泽便多叫上几个学弟学妹和她一同前往飞往东京，其中就有嘉欢学姐，晴晴学姐，耀星学长。但是因为在买机票的时候有些失误，她没有和她们三挨在一起，但是飞机上媛泽感到非常寂寞，想要到她们仨任意一人的位置上去一起坐这次的长途飞机，飞机上位置看作一个1212*1212的矩阵，其中ZHQXJF分别表示媛泽，嘉欢，晴晴，耀星，日本人，其他乘客的位置，并且没有位置被空缺出来。在前往任意一个学弟或学妹的位置的时候会经过其它乘客，由于媛泽穿了漂亮的jk害怕飞机上的小日子过得还不错的日本人骚扰她，所以在前往学弟学妹的位置的过程中会尽力避开日本人和挨着日本人的乘客，聪明的你来帮帮媛泽躲开日本人并计算出可以到达的且离她最近的学弟或学妹与她的距离。

Input

输入1212*1212的字符矩阵来表示灰机的座位关系。

Output

如果媛泽能够避开日本人到达他们三之中任意一人的位置上时，输出最短距离，否则输出0。

Sample Input 1

ZFJFHFFFFFFF
FFFFFFFFFFFF
FFFFFFFFFFFF
FFFFFJFFFFFF
FJFFFFFFFFFF
FFFFFFFFFFFF
FFFFFFFFFFFF
FFFFFJFFFFFF
FJFFFFFFFFFF
FFFQFFFFFFFF
FFFFFFFFFFFF
FFXFFFFFFFFF

Sample Output 1

12

Hint

如果媛泽周围八个方向上已经有日本人了，则媛泽不会动身，如果耀星，嘉欢，晴请也都是这般情况，也视为不可达，以上情况则输出0.

解题思路：

很明显，这道题的解题思路依旧是运用BFS，我们需要一个结构体来存储我们的位置，和已经走过的步数，需要一个队列来存储我们现在的位置和相邻的位置，直到目的地址进入队列。
但这道题难的地方不是在写BFS的逻辑上面，而是在怎么判断相邻位置应不应该入队。由题意可知，入队的位置其周围的八个位置都不应该出现日本人”J”，但是有特例啊，比如在边缘的地方，他周围能坐人的地方都只有3个或5个，不可能这种地方也要判断8个方位吧，所以就要分区域了，不同区域的判断条件都不同，如下图：

按照这样划分的话，区域1需要判断3个方向，区域2需要判断5个方向，方向图如下：

这样下来判断语句就显得非常臃肿(一下是我在考核时写的)：

bool judge(path n){
    if(n.x<12&&n.y<12&&n.x>=0&&n.y>=0&&map[n.x][n.y]!='J'){
        if(n.x<11&&n.y<11&&n.x>=1&&n.y>=1&&map[n.x][n.y+1]!='J'&&map[n.x+1][n.y+1]!='J'&&map[n.x+1][n.y]!='J'&&map[n.x+1][n.y-1]!='J'&&map[n.x][n.y-1]!='J'&&map[n.x-1][n.y-1]!='J'&&map[n.x-1][n.y]!='J'&&map[n.x-1][n.y+1]!='J'){
            return true;
        }else if(n.x<11&&n.y<12&&n.x>=1&&n.y>=11&&map[n.x+1][n.y]!='J'&&map[n.x+1][n.y-1]!='J'&&map[n.x][n.y-1]!='J'&&map[n.x-1][n.y-1]!='J'&&map[n.x-1][n.y]!='J'){
            return true;
        }else if(n.x<12&&n.y<11&&n.x>=11&&n.y>=1&&map[n.x][n.y+1]!='J'&&map[n.x][n.y-1]!='J'&&map[n.x-1][n.y-1]!='J'&&map[n.x-1][n.y]!='J'&&map[n.x-1][n.y+1]!='J'){
            return true;
        }else if(n.x<11&&n.y<1&&n.x>=1&&n.y>=0&&map[n.x][n.y+1]!='J'&&map[n.x+1][n.y+1]!='J'&&map[n.x+1][n.y]!='J'&&map[n.x-1][n.y]!='J'&&map[n.x-1][n.y+1]!='J'){
            return true;
        }else if(n.x<1&&n.y<11&&n.x>=0&n.y>=1&&map[n.x][n.y+1]!='J'&&map[n.x+1][n.y+1]!='J'&&map[n.x+1][n.y]!='J'&&map[n.x+1][n.y-1]!='J'&&map[n.x][n.y-1]!='J'){
            return true;
        }else if(n.x==0&&n.y==11&&map[n.x+1][n.y]!='J'&&map[n.x+1][n.y-1]!='J'&&map[n.x][n.y-1]!='J'){
            return true;
        }else if(n.x==11&&n.y==11&&map[n.x+1][n.y-1]!='J'&&map[n.x][n.y-1]!='J'&&map[n.x-1][n.y-1]!='J'){
            return true;
        }else if(n.x==11&&n.y==0&&map[n.x][n.y+1]!='J'&&map[n.x-1][n.y]!='J'&&map[n.x-1][n.y+1]!='J'){
            return true;
        }else if(n.x==0&&n.y==0&&map[n.x][n.y+1]!='J'&&map[n.x+1][n.y+1]!='J'&&map[n.x+1][n.y]!='J'){
            return true;
        }
    }
    return false;
}

就问你这看的难不难受！
于是最后系统判我超时了，非常难受！
回到寝室后，我又继续想这道题该怎么写，于是我想到了一个好办法：将该矩阵扩展到14x14，外面的一圈用”F”填充，中央的才是我们的飞机座位表，这样我们原本处于边缘的位置就不再是边缘了，而且其新填的位置都不是日本人，这样我们的判断条件对于12x12矩阵中的每一个元素都是适用的。还有最重要的一点就是走过的路不能重复走，得写一个布尔类型的矩阵，这个当时我忘了，所以铁定超时！

新的判断条件：

remap[n.x][n.y]==false&&n.x<13&&n.y<13&&n.x>=1&&n.y>=1&&map[n.x][n.y]!='J'&&map[n.x][n.y+1]!='J'&&map[n.x+1][n.y+1]!='J'&&map[n.x+1][n.y]!='J'&&map[n.x+1][n.y-1]!='J'&&map[n.x][n.y-1]!='J'&&map[n.x-1][n.y-1]!='J'&&map[n.x-1][n.y]!='J'&&map[n.x-1][n.y+1]!='J'

源码：

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
bool remap[14][14];
char map[14][14];
struct path{
    int x;
    int y;
    char vul;
    int count;
};
queue<path> q;
int M[4][2]={0,1,1,0,0,-1,-1,0};
int go(path s){
    path now,n;
    remap[s.x][s.y]=true;
    q.push(s);
    while (!q.empty())
    {
        now=q.front();
        if(now.vul=='H'||now.vul=='X'||now.vul=='Q'){
            return now.count;
        }
        for(int i=0;i<4;i++){
            n.x=M[i][0]+now.x;
            n.y=M[i][1]+now.y;
            if(remap[n.x][n.y]==false&&n.x<13&&n.y<13&&n.x>=1&&n.y>=1&&map[n.x][n.y]!='J'&&map[n.x][n.y+1]!='J'&&map[n.x+1][n.y+1]!='J'&&map[n.x+1][n.y]!='J'&&map[n.x+1][n.y-1]!='J'&&map[n.x][n.y-1]!='J'&&map[n.x-1][n.y-1]!='J'&&map[n.x-1][n.y]!='J'&&map[n.x-1][n.y+1]!='J'){
                n.vul=map[n.x][n.y];
                n.count=now.count+1;
                q.push(n);
                remap[n.x][n.y]=true;
            }
        }
        q.pop();
    }
    return 0;
}
int main(){
    path s;
    memset(map,'F',sizeof(map));
    memset(remap,false,sizeof(remap));
    for(int i=1;i<13;i++){
        for(int j=1;j<13;j++){
            cin>>map[i][j];
            if(map[i][j]=='Z'){
                s.x=i;
                s.y=j;
                s.vul='Z';
                s.count=0;
            }
        }
    }
    cout<<go(s);
    return 0;
}