2501 矩阵距离 (bfs)
2024-10-15 14:49:03
描述
给定一个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();
}
最新文章
- nginx 和 IIS 实现负载均衡
- SystemTap知识(一)
- AngularJs编写指令
- C++ deepin
- C++ 文件流的方式操作文件(一个简单的写入,读取)
- Redis .NET操作
- bugku 密码学一些题的wp
- mysql正则表达式无法识别\d
- P1220 关路灯 区间dp
- window.open 和showModalDialog的返回值
- 移动端(处理边距样式)reset.css
- Go语言程序结构分析初探
- Linux Centos关机命令
- 课程一(Neural Networks and Deep Learning),第二周(Basics of Neural Network programming)—— 0、学习目标
- Elasticsearch Java Rest Client API 整理总结 (三)——Building Queries
- RAC迁移至单机考虑几大因素
- PHP中curl的使用
- SAP middb主键加索引
- .net core执行dotnet ef migrations createmodel等命令出错
- [转]改变UITextField placeHolder颜色、字体
热门文章
- Confluence 6 使用一个主题到站点
- js之DOM对象三
- 论文阅读:Review of Visual Saliency Detection with Comprehensive Information
- java----AOP框架理解
- 多版本python安装第三方库
- wampserver本地配置域名映射
- 如果拷贝项目出现各种找不到文件的时候,基本就是没有标记,或者文件名的问题,Could not find resource mybatis.xml,解决方法
- HDU 3294 Girls' research(manachar模板题)
- expect 安装 salt 客户端
- JAVA二分搜索树