首页 > 代码库 > POJ 2049 Finding Nemo BFS

POJ 2049 Finding Nemo BFS

2024-07-05 22:22:49   229人阅读

题目大意：给你一个奇奇怪怪的迷宫， 这个迷宫包括墙和门。再给你一个起始坐标， 问你从迷宫内到外面至少要穿越多少的门。

题目分析：

穿越多少门等同于路过了多少个格子。

为此我们可以将整个地图中的格子，门，墙，墙的交界处（格子的顶点）全部抽象成点。

即坐标（奇数，奇数）为格子的坐标，坐标（奇数，偶数）或坐标（偶数，奇数）为门或墙的坐标，坐标（偶数，偶数）为格子的顶点。

这样题目就转化成了从起始点所在的格子走到迷宫外的格子最少要经过多少个格子，用step[i][j]表示走出迷宫后遇到的第一个格子的坐标走过的步数,那么答案就是step[i][j] / 2（步数等于走过格子数+穿越的门数，且门数恰好等于格子数，读者可以自行思考一下）。

在此先提醒一点：题目给的坐标是（列，行），而我的数组全部用的[行][列]，所以需要转化一下， 千万不要搞错了。

解题方法：

用map[405][405]保存抽象后的地图。其中map[i][j] = -1表示墙，map[i][j] = 1表示门，map[i][j] = 0表示在迷宫内的格子，map[i][j] = 2表示在迷宫外的格子。

则给的第一组样例用10*10的局部图表示如下（下标从0开始）：

注意当给出的起始点的坐标并无范围限制，所以需要特判当x或y坐标小于0或者大于199时便直接输出0，因为已经在迷宫外了。

顺带一提，这样的解法并不优秀，仅做参考。

代码如下：

//思路：把边和点都抽象成点
#include <stdio.h>
#include <string.h>
#define MS0(X) memset(X, 0, sizeof X)
const int O = 1000000;
const int maxn = 405;
int path[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int map[maxn][maxn];//2 = out   |   0 = in   |   -1 = wall   |   1 = door
int step[maxn][maxn];
bool vis[maxn][maxn];
typedef struct queue{
    int x, y;
}queue;
queue Q[O];
int head, tail;
int n, m;
void print_map(){
    for(int i = 9; i >= 0; --i){
        for(int j = 0; j < 10; ++j) printf("%3d", map[i][j]);
        printf("\n\n");
    }
}
void BFS1(int x, int y){//将map的外部染成2
    if(map[x][y] == 2) return;//已经走过了
    head = tail = 0;
    queue q = {x, y};
    map[x][y] = 2;
    Q[tail++] = q;
    while(head != tail){
        q = Q[head++];
        for(int k = 0; k < 4; ++k){
            int nx = q.x + path[k][0], ny = q.y + path[k][1];
            if(nx >= 0 && ny >= 0 && nx < maxn && ny < maxn && !map[nx][ny]){
                map[nx][ny] = 2;
                queue tmp = {nx, ny};
                Q[tail++] = tmp;
            }
        }
    }
    //print_map();
}
int BFS2(int x, int y){
    if(map[x][y] == 2) return 0;// already out
    MS0(vis);
    MS0(step);
    head = tail = 0;
    queue q = {x, y};
    vis[x][y] = 1;
    step[x][y] = 0;
    Q[tail++] = q;
    while(head != tail){
        q = Q[head++];
        //printf("q.x = %d, q.y = %d\n", q.x, q.y);
        if(map[q.x][q.y] == 2) return step[q.x][q.y] / 2;//已经走出去了
        for(int k = 0; k < 4; ++k){
            int nx = q.x + path[k][0], ny = q.y + path[k][1];
            if(nx >= 0 && ny >= 0 && nx < maxn && ny < maxn && !vis[nx][ny] && ~map[nx][ny]){
                step[nx][ny] = step[q.x][q.y] + 1;
                vis[nx][ny] = 1;
                queue tmp = {nx, ny};
                Q[tail++] = tmp;
            }
        }
    }
    return -1;
}
void work(){
    int x, y, d, t;
    double fx, fy;
    MS0(map);
    for(int i = 0; i < maxn; i += 2) for(int j = 0; j < maxn; j += 2) map[i][j] = -1;
    for(int i = 0; i < n; ++i){
        scanf("%d%d%d%d", &y, &x, &d, &t);
        x <<= 1;
        y <<= 1;
        t <<= 1;
        map[x][y] = -1;
        for(int i = 1; i <= t; ++i) d ? (map[x + i][y] = -1) : (map[x][y + i] = -1);
    }
    for(int i = 0; i < m; ++i){
        scanf("%d%d%d", &y, &x, &d);
        x <<= 1;
        y <<= 1;
        d ? (map[x + 1][y] = 1) : (map[x][y + 1] = 1);
    }
    scanf("%lf%lf", &fy, &fx);
    x = fx;
    y = fy;
    if(fx < 0 || fx > 199 || fy < 0 || fy > 199){
        printf("0\n");
        return;
    }
    x = (x << 1) ^ 1;//x = x * 2 + 1;
    y = (y << 1) ^ 1;//y = y * 2 + 1;
    BFS1(1, 1); BFS1(1, 401); BFS1(401, 1); BFS1(401, 401);//将迷宫外的非抽象后的顶点的点全部染色
    printf("%d\n", BFS2(x, y));
}
int main(){
    while(~scanf("%d%d", &n, &m) && (~n || ~m)) work();
    return 0;
}
POJ 2049

 

 


联系
我们