acwing 173 矩阵距离

简介: acwing 173 矩阵距离

173. 矩阵距离 - AcWing题库

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std ;
const int N = 1010 ;
int d[4][2] = {{1,0},{-1,0},{0,-1},{0,1}} ;
struct node{
  int x,  y ;
  node(int xx ,int yy ){
    x = xx , y = yy ;
  }
};
char g[N][N] ;
int n , m ;
int dis[N][N] ;
int v[N][N] ;
queue<node> q ;
void bfs(){
  while(!q.empty()){
    node now = q.front() ;
    q.pop() ;
    int x = now.x , y = now.y ;
    for(int i = 0 ;  i < 4 ; i ++){
      int tx = x + d[i][0] , ty = y + d[i][1] ;
      if(tx<0||tx>=n||ty<0||ty>=m||dis[tx][ty]!=-1) continue ;
      dis[tx][ty] = dis[x][y] + 1 ;
      q.push(node(tx,ty)) ;
    }
  }
}
int main(){
  cin >> n >> m ;
  memset(dis,-1,sizeof(dis)) ;
  for(int i = 0 ; i < n ;i ++) cin >> g[i] ;
  for(int i = 0 ; i < n ; i++){
    for(int j = 0 ; j < m ;j ++){
      if(g[i][j] == '1') dis[i][j] = 0 , q.push(node(i,j)) ;
    } 
  }
  bfs() ;
  for(int i = 0 ; i < n ; i ++){
    for(int j = 0 ; j < m ; j ++){
      cout << dis[i][j] << " " ;
    }cout << endl ;
  }
} 
目录
相关文章
|
7月前
|
算法 测试技术 C#
【二分查找】LeetCode1970:你能穿过矩阵的最后一天
【二分查找】LeetCode1970:你能穿过矩阵的最后一天
|
7月前
矩阵 螺旋矩阵
矩阵 螺旋矩阵
50 2
|
7月前
leetcode-542:01 矩阵
leetcode-542:01 矩阵
42 0
|
算法 C++
【每日算法Day 64】LeetCode 861. 翻转矩阵后的得分
【每日算法Day 64】LeetCode 861. 翻转矩阵后的得分
|
Java C++
环形矩阵(螺旋矩阵)&&蛇形矩阵
环形矩阵(螺旋矩阵)&&蛇形矩阵
148 0
LeetCode 1329. 将矩阵按对角线排序
矩阵对角线 是一条从矩阵最上面行或者最左侧列中的某个元素开始的对角线,沿右下方向一直到矩阵末尾的元素。
111 0
Acwing 平方矩阵 C++
Acwing 平方矩阵 C++
130 0
Acwing 平方矩阵 C++
AcWing 617. 距离
AcWing 617. 距离
77 0
AcWing 617. 距离
AcWing 755. 平方矩阵 III
AcWing 755. 平方矩阵 III
88 0
AcWing 755. 平方矩阵 III
AcWing 753. 平方矩阵 I
AcWing 753. 平方矩阵 I
72 0
AcWing 753. 平方矩阵 I