AcWing 173. 矩阵距离

古城微笑少年丶 2024-04-08 13:17 71阅读 0赞

## AcWing 173. 矩阵距离 ##

### 原题链接 ###

[AcWing 173. 矩阵距离][AcWing 173.]

### 算法标签 ###

BFS 多源BFS

### 题意解释 ###

求每个位置到所有1距离中的最短距离

### 思路 ###

#### 多源BFS ####

只有单源的入口节点（下图第一部分），按照BFS套路（每次由起点外扩展， 队列会在X的基础上，新增距离为X+1的一段， 即为两段性与单调（递增）性），从而求出最短路之类的问题  
![请添加图片描述][7c66701b0c8d44a3a0cc54bc58dd20c7.png]  
![请添加图片描述][26b2478bb95d4cc4b5d7bfd4d23a00bf.png]

#### 具体思路 ####

![请添加图片描述][b98143ed14fa43fb834a51410eeee0c1.png]

### 代码 ###

#include<bits/stdc++.h>
    #define int long long
    #define rep(i, a, b) for(int i=a;i<b;++i)
    #define Rep(i, a, b) for(int i=a;i>b;--i)
    #define x first
    #define y second
    using namespace std;
    typedef pair<int, int> PII;
    int dx[4]={-1, 0, 1, 0}, dy[4]={0, -1, 0, 1};
    const int N = 1005;
    int n,m;
    char g[N][N];
    int d[N][N];
    PII q[N*N];
    inline int read(){
       int s=0,w=1;
       char ch=getchar();
       while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
       while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
       return s*w;
    }
    void put(int x) {
        if(x<0) putchar('-'),x=-x;
        if(x>=10) put(x/10);
        putchar(x%10^48);
    }
    void bfs(){
    	// 注意 这里队尾为-1
    	// 其他初始为0是因为main里面传了一个值作为队尾，即传入的 q[0] 是队尾，但这没有传值，若tt从 0 开始，++ tt 就会导致 q[0] 这个位置为空，所以下标从 -1 开始
        int hh=0, tt=-1;
        memset(d, -1, sizeof d);
        // 将所有
        rep(i, 0, n){
            rep(j, 0, m){
                if(g[i][j]=='1'){
                    d[i][j]=0;
                    q[++tt]={i, j};
                }
            }
        }
        while(hh<=tt){
            PII t=q[hh++];
            rep(i, 0, 4){
                int x=t.x+dx[i], y=t.y+dy[i];
                if(x<0||x>=n||y<0||y>=m){
                    continue;
                }
                if(d[x][y]!=-1){
                    continue;
                }
                d[x][y]=d[t.x][t.y]+1;
                q[++tt]={x, y};
            }
        }
    }
    signed main(){
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);
    	n=read(), m=read();
    	rep(i, 0, n){
    	    scanf("%s", g[i]);
    	}
    	bfs();
    	rep(i, 0, n){
    	    rep(j, 0, m){
    	        printf("%lld ", d[i][j]);
    	    }
    	    puts("");
    	}
    	return 0;
    }

参考文献

[AcWing 173. 矩阵距离（算法提高课）视频讲解][AcWing 173. 1]  
[AcWing 173. 矩阵距离（算法提高课）代码][AcWing 173. 2]

原创不易  
转载请标明出处  
如果对你有所帮助 别忘啦点赞支持哈  
![在这里插入图片描述][9cb4cb80a18345158f8a69e2f196e5b9.png]

[AcWing 173.]: https://www.acwing.com/problem/content/175/
[7c66701b0c8d44a3a0cc54bc58dd20c7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/0d9c3b79a5a94493b0cec0a854cdb29f.png
[26b2478bb95d4cc4b5d7bfd4d23a00bf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/e75ebfc5ce2049c78a7cf3cce04cdfbd.png
[b98143ed14fa43fb834a51410eeee0c1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/8b3ae45fd77646ea8405d21fedd4a714.png
[AcWing 173. 1]: https://www.acwing.com/video/453/
[AcWing 173. 2]: https://www.acwing.com/activity/content/code/content/131617/
[9cb4cb80a18345158f8a69e2f196e5b9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/cfa1e7fdfdf7462e9225e7f7c7ce528c.png