BFS简单题套路_Codevs 1215 迷宫

BFS 简单题套路

1. 遇到迷宫之类的简单题，有什么行走方向的，先写下面的 声明

const int maxn = ;

struct Status {

    int r, c;

    Status(int r = , int c = ) : r(r), c(c) {}

//    int DIR;

};

int N;                   //迷宫数量

int W;                   //迷宫宽度

char map[maxn][maxn];    //地图

//方向 : 分别代表 上、右、下、左向量

int dir[][] = { {-, }, {, }, {, }, {, -} };

bool vis[maxn][maxn];

//队列

queue<Status> que;

void input();            //输入数据

bool judge(int r, int c);//判断是否越界, 是否是路

bool check(int r, int c);//判断当前是否到达终点

//移动一步

void Move(const Status& now, int r, int c, int k);

void BFS();              //BFS搜索

void solve();  

2. 随后再逐个函数的实现

//完整代码

/*

 * Codevs 1215 迷宫

 */

#include <iostream>

#include <queue>

#include <cstring>

#include <cstdio>

#include <cstdlib>

using namespace std;

const int maxn = ;

struct Status {

    int r, c;

    Status(int r = , int c = ) : r(r), c(c) {}

//    int DIR;

};

int N;                   //迷宫数量

int W;                   //迷宫宽度

char map[maxn][maxn];    //地图

//方向 : 分别代表 上、右、下、左向量

int dir[][] = { {-, }, {, }, {, }, {, -} };

bool vis[maxn][maxn];

//队列

queue<Status> que;

void input();            //输入数据

bool judge(int r, int c);//判断是否越界, 是否是路

bool check(int r, int c);//判断当前是否到达终点

//移动一步

void Move(const Status& now, int r, int c, int k);

void BFS();              //BFS搜索

void solve();            //启动

void input()

{

    memset(map, , sizeof(map));

    memset(vis, , sizeof(vis));

    while (!que.empty()) que.pop();

    scanf("%d", &W);

    getchar();

    for (int i = ; i < W; i++) {

        scanf("%s", map[i]);

    }

}

bool judge(int r, int c)

{

    return (r >=  && r < W) && (c >=  && c < W)

            && map[r][c] != '#';

}

bool check(int r, int c)

{

    return (r == W- && c == W-) && map[r][c] == 'e';

}

void Move(const Status& now, int r, int c, int k)

{

    Status tmp = now;

    int tmpx = tmp.r;

    int tmpy = tmp.c;

    tmpx += dir[k][];

    tmpy += dir[k][];

    //判断是否越界, 是否是路, 是否走过

    if (!judge(tmpx, tmpy) || vis[tmpx][tmpy]) return;

    if (check(tmpx, tmpy)) {

        printf("YES\n");

        exit();

    }

    vis[tmpx][tmpy] = true;

    que.push(Status(tmpx, tmpy));

}

void BFS()

{

    que.push(Status(, ));

    while (!que.empty())

    {

        Status now = que.front(); que.pop();

        int r = now.r, c = now.c;

        for (int k = ; k < ; k++) {

            Move(now, r, c, k);

        }

    }

    printf("NO\n");

}

void solve()

{

    scanf("%d", &N);

    while (N--) {

        input();

        BFS();

    }

}

int main()

{

    solve();

    return ;

}