标签：自己   时间   can   mys   ace   代码   数据   code   vector   

题目传送门

今天考试的t1

某位菜鸡考的时候只做了20分

题意：对于给定的01矩阵，求出矩阵上所有点到其最近的1的曼哈顿距离。

思路：

考试的时候看完题，嗯？广搜水题？然后几分钟就打完了那段20分的拙劣代码。最初始的想法：对于每个0点，跑一边bfs即可，时间复杂度O(\(n^2\))，打完觉得不太对，可能会挂，然后改成了对于每个1点，用bfs去遍历更新其他点的最小值，然而时间复杂度似乎没差，自己测的数据还是会T,但抱着侥幸的心理想着应该不会挂太多的点吧……然后就20分了。

[正确的解法]合理利用bfs的层次单调性，对于一个无向无边权值的矩阵，bfs每次更新的一定是当前能更新到的最短距离，所以只需要将所有的1的点放入队列中，然后跑bfs即可。。。（这么简单还想不到，我真是菜啊）

Code:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
//Mystery_Sky
//
#define M 1000101
#define INF 0x3f3f3f3f
#define ll long long
inline int read()
{
    int x=0, f=1;char c=getchar();
    while(c'9') {if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c Q;
inline void bfs()
{
    while(!Q.empty()) {
        node top = Q.front();
        Q.pop();
        for(int i = 0; i  n || yy  m) continue;
            if(ans[xx][yy] == INF) ans[xx][yy] = top.step + 1, Q.push((node) {xx, yy, top.step + 1}); 
        }
    }
}

int main() {
    n = read(), m = read(); 
    memset(ans, INF, sizeof(ans));
    for(int i = 1; i 

AcWing 173. 矩阵距离

标签：自己   时间   can   mys   ace   代码   数据   code   vector   

原文地址：https://www.cnblogs.com/Benjamin-cpp/p/11380159.html