MENU

2018年北京信息科技大学第十届程序设计竞赛A PUBG(bfs)

2018 年 05 月 10 日 • 阅读: 1088 • 图论阅读设置

PUBG

  • 时间限制:C/C++ 1秒,其他语言2秒
  • 空间限制:C/C++ 32768K,其他语言65536K
  • 64bit IO Format: %lld

题目描述

最近,喜爱ACM的PBY同学沉迷吃鸡,无法自拔,于是又来到了熟悉的ERANGEL。经过一番搜寻,PBY同学准备动身前往安全区,但是,地图中埋伏了许多LYB,PBY的枪法很差,希望你能够帮他找到一条路线,每次只能向上、下、左、右移动,尽可能遇到较少的敌人。

输入描述

题目包含多组测试,请处理到文件结束;
第一行是一个整数n,代表地图的大小;
接下来的n行中,每行包含n个整数a,每个数字a代表当前位置敌人的数量;
1 < n <= 100,1 <= a <= 100,-1代表当前位置,-2代表安全区。

输出描述

对于每组测试数据,请输出从当前位置到安全区所遇到最少的敌人数量,每个输出占一行。

输入

5
6 6 0 -2 3
4 2 1 2 1
2 2 8 9 7
8 1 2 1 -1
9 7 2 1 2

输出

9

输入

5
62 33 18 -2 85
85 73 69 59 83
44 38 84 96 55
-1 11 90 34 50
19 73 45 53 95

输出

173

链接

https://www.nowcoder.com/acm/contest/118/A

题意

问从一点走到另一点遇到的最少的敌人的数量。

题解

BFS搜索,用$ans[i][j]$表示从起点(sx, sy)走到(i, j)遇到的敌人数量,$G[i][j]$表示(i, j)位置现有敌人数量,设当前位置(a.x, a.y),下一步(b.x, b.y)。

若$ans[i][j] + G[b.x][b.y] < ans[b.x][b.y]$,则更新$ans[b.x][b.y] = ans[i][j] + G[b.x][b.y]$。

代码

运行时间(ms)使用内存(KB)代码长度
8715081381
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 110;
int G[maxn][maxn];
int ans[maxn][maxn];
int dir[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
int n, sx, sy, ex, ey;

struct Node
{
    int x, y;
};

void bfs()
{
    queue <Node> q;
    Node a, b;
    a.x = sx, a.y = sy;
    ans[a.x][a.y] = 0;
    q.push(a);
    while (!q.empty())
    {
        a = q.front();
        q.pop();
        for (int i = 0; i < 4; ++i)
        {
            b.x = a.x + dir[i][0], b.y = a.y + dir[i][1];
            if (b.x < 1 || b.x > n || b.y < 1 || b.y > n) // 越界
                continue;
            if (ans[a.x][a.y] + G[b.x][b.y] < ans[b.x][b.y]) // 更新
            {
                ans[b.x][b.y] = ans[a.x][a.y] + G[b.x][b.y];
                q.push(b);
            }
        }
    }
}

int main()
{
    while (scanf("%d", &n) != EOF)
    {
        memset(ans, inf, sizeof(ans));
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                scanf("%d", &G[i][j]);
                if (G[i][j] == -1)
                    sx = i, sy = j, G[i][j] = 0;
                else if (G[i][j] == -2)
                    ex = i, ey = j, G[i][j] = 0;
            }
        }
        bfs();
        printf("%d\n", ans[ex][ey]);
    }
    return 0;
}

队友说转化为图论求最短路,Dijkstra使用优先队列也可以过。


The end.
2018-05-10 星期四
最后编辑于: 2018 年 11 月 01 日