主页 / 问题 / 1586250
Accepted
Kirill
Asked:2024-07-05 20:35:36 +0000 UTC2024-07-05 20:35:36 +0000 UTC

BFS，解决矩阵遍历问题

  • 772

我的代码解决了这个问题在此输入图像描述

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;

    vector <vector<int>> g(n+1, vector<int> (m+1, 0));
    vector <vector<int>> matrix(n+1, vector<int> (m+1, 0));
    queue <pair<int, int>> q;

    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++)
        {
            cin >> g[i][j];
            if(g[i][j] == 1) q.push({i, j});
        }
    
    vector <int> x = {1, -1, 0, 0};
    vector <int> y = {0, 0, 1, -1};

    while(!q.empty())
    {
        auto t = q.front();
        q.pop();
        int t_x = t.first, t_y = t.second;

        for(int i = 0;i < 4;i++)
        {
            int xx = t_x + x[i], yy = t_y + y[i];
            if(xx > 0 && xx <= n && yy > 0 && yy <= m && matrix[xx][yy] == 0)
            {
                matrix[xx][yy] = matrix[t_x][t_y] + 1;
                q.push({xx, yy});
            }
        }
    }
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= m;j++)
        {
            if(g[i][j] == 0)
                cout << matrix[i][j] << " ";
            else
                cout << 0 << " ";
        }   
        cout << endl;
    }
}

该解决方案在某些测试中捕获了 WA，可能是什么错误？

c++

1 个回答

  1. Best Answer

    用大量数字填充矩阵

    我们重置单元格g[i][j] == 1

    走来走去时

            matrix[xx][yy] = min(matrix[xx][yy], matrix[t_x][t_y] + 1);
    • 0

相关问题