描述

给定一个N行M列的01矩阵 A,A[i][j] 与 A[k][l] 之间的曼哈顿距离定义为:
dist(A[i][j],A[k][l])=|i-k|+|j-l|

输出一个N行M列的整数矩阵B,其中:
B[i][j]=min(1≤x≤N,1≤y≤M,A[x][y]=1)⁡{dist(A[i][j],A[x][y])}
即求与每个位置曼哈顿距离最近的1
N,M≤1000。

输入格式

第一行两个整数n,m。

接下来一个N行M列的01矩阵,数字之间没有空格。

输出格式

一个N行M列的矩阵B,相邻两个整数之间用一个空格隔开。

样例输入

3 4
0001
0011
0110

样例输出

3 2 1 0
2 1 0 0
1 0 0 1 思路:直接对每个1的起点bfs,搜过的点就不用搜了,每个第一次遍历的点,就是其中一个起点到其的最小曼哈顿距离
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
vector<P>v;
int r,c;
char maps[][];
int vis[][];
int way[][] = {,,-,,,,,-};
struct Node
{
int x,y;
};
int num;
void init()
{
scanf("%d%d",&r,&c);
char s[];
for(int i=;i<=r;i++)
{
scanf("%s",s);
for(int j=;j<=c;j++)
{
maps[i][j] = s[j-];
if(maps[i][j] == '')
{
num++;
v.push_back(P(i,j));
vis[i][j] = ;
}
}
}
} void bfs()
{
queue<P>que;
while(!que.empty())que.pop();
for(int i=;i<v.size();i++)que.push(v[i]);
while(!que.empty())
{
P tmp = que.front();
que.pop();
for(int i=;i<;i++)
{
int xx = tmp.first + way[i][];
int yy = tmp.second + way[i][];
if(xx >= && xx <= r && yy >= && yy <= c && !vis[xx][yy])
{
num++;
vis[xx][yy] = vis[tmp.first][tmp.second] + ;
que.push(P(xx,yy));
}
}
if(num == r * c)return;
}
} void print()
{
for(int i=;i<=r;i++)
{
for(int j=;j<=c;j++)
{
printf(j==c?"%d\n":"%d ",vis[i][j]-);
}
}
}
int main()
{
init();
bfs();
print();
}

最新文章

  1. nginx 和 IIS 实现负载均衡
  2. SystemTap知识(一)
  3. AngularJs编写指令
  4. C++ deepin
  5. C++ 文件流的方式操作文件(一个简单的写入,读取)
  6. Redis .NET操作
  7. bugku 密码学一些题的wp
  8. mysql正则表达式无法识别\d
  9. P1220 关路灯 区间dp
  10. window.open 和showModalDialog的返回值
  11. 移动端(处理边距样式)reset.css
  12. Go语言程序结构分析初探
  13. Linux Centos关机命令
  14. 课程一(Neural Networks and Deep Learning),第二周(Basics of Neural Network programming)—— 0、学习目标
  15. Elasticsearch Java Rest Client API 整理总结 (三)——Building Queries
  16. RAC迁移至单机考虑几大因素
  17. PHP中curl的使用
  18. SAP middb主键加索引
  19. .net core执行dotnet ef migrations createmodel等命令出错
  20. [转]改变UITextField placeHolder颜色、字体

热门文章

  1. Confluence 6 使用一个主题到站点
  2. js之DOM对象三
  3. 论文阅读:Review of Visual Saliency Detection with Comprehensive Information
  4. java----AOP框架理解
  5. 多版本python安装第三方库
  6. wampserver本地配置域名映射
  7. 如果拷贝项目出现各种找不到文件的时候,基本就是没有标记,或者文件名的问题,Could not find resource mybatis.xml,解决方法
  8. HDU 3294 Girls' research(manachar模板题)
  9. expect 安装 salt 客户端
  10. JAVA二分搜索树