随机到一道普及组题目,不容易啊(水博客真开心系列)

1. 题目

传送门= ̄ω ̄=

2. 题解

把所有的 1 位置丢到队列里 Bfs 就行啦= ̄ω ̄=

(这题我还 WA 了一次 T 了一次)

#include <bits/stdc++.h>

#define NS (1005)

using namespace std;

const int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, m, dis[NS][NS], x[NS * NS], y[NS * NS], front, tail;

char str[NS];

void Bfs()
{
    while (front < tail)
    {
        for (int i = 0; i < 4; i += 1)
        {
            int nx = x[front] + dx[i], ny = y[front] + dy[i];
            if (nx < 1 || nx > n || ny < 1 || ny > m || dis[nx][ny] < 1e9)
                continue;
            dis[nx][ny] = dis[x[front]][y[front]] + 1;
            x[tail] = nx, y[tail++] = ny;
        }
        front++;
    }
}

int main(int argc, char const* argv[])
{
    IN(n), IN(m), memset(dis, 0x3f, sizeof(dis));
    for (int i = 1; i <= n; i += 1)
    {
        scanf("%s", str + 1);
        for (int j = 1; j <= m; j += 1)
            if (str[j] == '1') dis[i][j] = 0, x[tail] = i, y[tail++] = j;
    }
    Bfs();
    for (int i = 1; i <= n; i += 1, putchar(10))
        for (int j = 1; j <= m; j += 1)
            printf("%d ", dis[i][j]);
    return 0;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注