173. 矩阵距离多源BFS的优化

题目

题解思路

先将所有要BFS源点入队，这样比一个一个的入队省了很多时间。

因为全部入队每次从最优的点跑出最优解。

而一次一次就是一个源点一遍一遍的跑全图。

AC代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

const  int  INF =  0x3f3f3f3f ;
const  int  N = 1010 ;

int minn[N][N] ;
char  mp[N][N] ;

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

int n , m ;
struct node
{
    int x,y,step ;
};



void bfs ( )
{
    queue  q ;
    for (int i = 0 ; i < n ; i++ )
        for (int j = 0 ; j < m ; j++ )
        {
            if ( mp[i][j] == '1' )
            {
                q.push({i,j,0}) ;
                minn[i][j] = 0 ;
            }
        }
    while(!q.empty())
    {
        node tmp = q.front();
        q.pop();
        for (int i = 0 ; i < 4 ; i++ )
        {
            int fx = tmp.x + dx[i] ;
            int fy = tmp.y + dy[i] ;
            if ( fx >= 0 && fy >= 0 && fx < n && fy < m && mp[fx][fy] == '0' && minn[fx][fy] > tmp.step + 1  )
            {
                minn[fx][fy] = tmp.step + 1 ;
                q.push({ fx ,fy,tmp.step + 1 } );
            }
        }
    }

}
int main ()
{
    ios::sync_with_stdio(false);
    cin >> n >> m ;
    for (int i = 0 ; i < n ; i++ )
            cin >> mp[i] ;
    for (int i = 0 ; i < n ; i++ )
        for (int j = 0 ; j < m ; j++ )
                minn[i][j] = INF ;
    bfs();
    for (int i = 0 ; i < n ; i++ )
    {
        for (int j = 0 ; j < m ; j++ )
            cout << minn[i][j] << " ";

        cout << "n" ;
    }
    return 0 ;
}

173. 矩阵距离 多源BFS的优化

C/C++/C#相关栏目本月热门文章

173. 矩阵距离多源BFS的优化