AcWing 173. 矩阵距离

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 173. 矩阵距离原题链接简单

作者：

Bug-Free , 2021-03-16 16:06:18 , 所有人可见 , 阅读 5939

71

23

#include <cstring>
#include <iostream>
#include <queue>

using namespace std;

const int N = 1e3 + 10;

int n, m;
char g[N][N];
int dist[N][N];

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

void bfs()
{
    queue<pair<int, int>> q;
    memset(dist, -1, sizeof dist);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (g[i][j] == '1') {
                q.push({i, j});
                dist[i][j] = 0;
            }
        }
    }

    while (q.size()) {
        auto t = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int x = t.first + dx[i], y = t.second + dy[i];
            if (x < 0 || x >= n || y < 0 || y >= m) {
                continue;
            }
            if (dist[x][y] == -1) {
                dist[x][y] = dist[t.first][t.second] + 1;
                q.push({x, y});
            }
        }
    }
}

int main()
{
    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        cin >> g[i];
    }

    bfs();

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (j > 0) {
                cout << " ";
            }
            cout << dist[i][j];
        }
        cout << endl;
    }

    return 0;
}

28 评论

legola 2023-02-28 22:52

几乎和大佬的代码一模一样，但为什么我的出现了段错误：

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int n, m;
char g[N][N];
int d[N][N];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
queue<pair<int, int>> q;

void bfs() {
    memset(d, -1, sizeof d);

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (g[i][j] == '1') {
                q.emplace(i, j);
                d[i][j] = 0;
            }

    while (!q.empty()) {
        auto &[x, y] = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < n && b >= 0 && b < m && d[a][b] == -1) {
                q.emplace(a, b);
                d[a][b] = d[x][y] + 1;
            }
        }
    }
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> g[i];

    bfs();

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << d[i][j] << ' ';
        }
        cout << "\n";
    }


    return 0;
}

legola 2023-02-28 22:53

我好像明白了，把[x, y]前的&去掉就行了，但不知道原理是什么

legola 2023-02-28 22:57 回复了 legola 的评论

由于 C++ STL 的 queue 的 push 和 pop 操作会改变容器内部的数据结构，因此在使用引用的方式访问 pair<int, int> 元素时，如果该元素已经被 pop 掉，则会访问到已经被释放的内存，从而导致段错误。因此在访问 queue 中的元素时，不建议使用引用的方式。

mCal 2022-08-02 17:29

有没有大佬说一下为什么二维矩阵用一重循环就初始化了

-_-_64 2022-08-04 00:08

是当成字符串输入那里么

-_-_64 2022-08-04 00:09

scanf(“%1d”,&a[i][j]);同样的效果

mCal 2022-08-04 15:12 回复了 -_-_64 的评论

蟹bro

不拿周赛牌不改名 2022-02-25 20:55

nice

wangtianyu 4个月前

请教一下那个等于负一是什么意思

Bug-Free 3个月前

还没有到过

炽热的秋冬 9个月前

先把所有1位置找到，放入队列搜索，这样搜索一次就可以得到最小距离了。每一个1的搜索都是最小距离。

污秽之翼 2023-10-28 19:15

数组模拟队列会超时 or2

水墨_w 9个月前

没有，还比这个要快一点

风天语 7个月前

可能是队列数组范围开太大了

Somebody1219 2023-09-10 21:29

几乎和大佬的代码一模一样，但为什么WA了：

#include<queue>
#include<cstring>
#include<iostream>
#include<map>
using namespace std;

const int N=1010;
int n,m;
typedef pair<int,int> PII;
queue<PII> q;
int dist[N][N];
char graph[N][N];
int count[N][N];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};

void bfs()
{
    while(q.size())
    {
        auto u=q.front();
        q.pop();
        int x=u.first,y=u.second;
        for(int i=0;i<4;i++)
        {
            if(x+dx[i]<0 || x+dx[i]>=m || y+dy[i]<0 || y+dy[i]>=n) continue;
            else{
                if(dist[x+dx[i]][y+dy[i]]==-1)
                {
                    dist[x+dx[i]][y+dy[i]]=dist[x][y]+1;
                    q.push({x+dx[i],y+dy[i]});
                }

            }
        }
    }

}
int main()
{
    memset(dist,-1,sizeof dist);

    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            cin>>graph[i][j];
            if(graph[i][j]=='1')
            {
                q.push({i,j});
                dist[i][j]=0;
            }

        }

    bfs();

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
            cout<<dist[i][j]<<' ';
        printf("\n");
    }
}