输入
第一行两个整数n,m。
接下来一个N行M列的01矩阵,数字之间没有空格。
数据范围
1≤N,M≤1000
输出
一个N行M列的矩阵B,相邻两个整数之间用一个空格隔开。每个整数表示加农势力存在的毫秒数(最小曼哈顿距离值)
输入样例 1
3 4 0001 0011 0110
输出样例 1
3 2 1 0 2 1 0 0 1 0 0 1
#include<bits/stdc++.h> using namespace std; int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1}; const int N=1010; char g[N][N]; int d[N][N],n,m; typedef pair<int,int> PII; queue<PII>q; void Build(int n,int m){ memset(d,-1,sizeof(d)); for(int i=0;i<n;i++) for(int j=0;j<m;j++){ char c = getchar(); while (c!='0' && c!='1'){ c = getchar(); } if(c=='1'){ d[i][j]=0; q.push(make_pair(i,j)); //压入队列,多源广搜 } } } void Print(int n,int m){ for(int i=0;i<n;i++){ for(int j=0;j<m;j++) cout<<d[i][j]<<' '; cout<<endl; } } void bfs(){ while(q.size()){ auto t=q.front(); q.pop(); int x=t.first,y=t.second; for(int i=0;i<4;i++){ int a=x+dx[i],b=y+dy[i]; if(a>=0 && a<n && b>=0&& b<m && d[a][b]==-1){ d[a][b]=d[x][y]+1; q.push({a,b}); } } } } int main() { cin>>n>>m; Build(n,m); bfs(); Print(n,m); return 0; }
腐烂的橘子
class Solution { int cnt; int dis[10][10]; int dir_x[4]={0, 1, 0, -1}; int dir_y[4]={1, 0, -1, 0}; public: int orangesRotting(vector<vector<int>>& grid) { queue<pair<int,int> >Q; memset(dis, -1, sizeof(dis)); cnt = 0; int n=(int)grid.size(), m=(int)grid[0].size(), ans = 0; for (int i = 0; i < n; ++i){ for (int j = 0; j < m; ++j){ if (grid[i][j] == 2){ Q.push(make_pair(i, j)); dis[i][j] = 0; } else if (grid[i][j] == 1) cnt += 1; } } while (!Q.empty()){ pair<int,int> x = Q.front();Q.pop(); for (int i = 0; i < 4; ++i){ int tx = x.first + dir_x[i]; int ty = x.second + dir_y[i]; if (tx < 0|| tx >= n || ty < 0|| ty >= m|| ~dis[tx][ty] || !grid[tx][ty]) continue; dis[tx][ty] = dis[x.first][x.second] + 1; Q.push(make_pair(tx, ty)); if (grid[tx][ty] == 1){ cnt -= 1; ans = dis[tx][ty]; if (!cnt) break; } } } return cnt ? -1 : ans; } }; 作者:LeetCode-Solution 链接:https://leetcode.cn/problems/rotting-oranges/solution/fu-lan-de-ju-zi-by-leetcode-solution/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
标签:cnt,tx,ty,int,bfs,grid,多源,dis From: https://www.cnblogs.com/weinan030416/p/17115425.html