【BZOJ 2252】 矩阵距离
2024-10-01 03:53:02
【题目链接】
https://www.lydsy.com/JudgeOnline/problem.php?id=2252
【算法】
将所有是”1“的点入队,然后广度优先搜索,即可
【代码】
#include<bits/stdc++.h>
using namespace std;
#define MAXN 1010 const int dx[] = {,,-,};
const int dy[] = {-,,,}; int i,j,n,m,tx,ty;
int dist[MAXN][MAXN];
char s[MAXN][MAXN];
char val;
pair<int,int> cur;
queue< pair<int,int> > q; inline bool ok(int x,int y)
{
return x >= && x <= n && y >= && y <= m;
} int main()
{
memset(dist,,sizeof(dist));
scanf("%d%d",&n,&m);
for (i = ; i <= n; i++) scanf("%s",s[i]+);
for (i = ; i <= n; i++)
{
for (j = ; j <= m; j++)
{
if (s[i][j] == '')
{
q.push(make_pair(i,j));
dist[i][j] = ;
}
}
}
while (!q.empty())
{
cur = q.front();
q.pop();
for (i = ; i < ; i++)
{
tx = cur.first + dx[i];
ty = cur.second + dy[i];
if (ok(tx,ty) && dist[tx][ty] == -)
{
dist[tx][ty] = dist[cur.first][cur.second] + ;
q.push(make_pair(tx,ty));
}
}
}
for (i = ; i <= n; i++)
{
for (j = ; j <= m; j++)
{
printf("%d ",dist[i][j]);
}
printf("\n");
} return ; }
最新文章
- java remote debug parameters
- hdu 2232 矩阵 ***
- webpack常用的插件安装命令
- sql删除多余重复的数据只保留一条
- Javascript之响应式相册
- Oracle基础学习1--Oracle安装
- TCP服务器端和客服端(一)
- [转]Linux下转换字符集(UTF8转换)
- 2014在百度之星资格赛的第二个问题Disk Schedule
- 使用WebGL加载Google街景图
- CentOS7开机提示welcome to emergency mode!after logging in...
- jQuery常用事件及扩展
- pycharm中运行时添加配置 及pytest模式怎么修改为run模式
- Java数据结构和算法 - 哈希表
- 机器学习基石笔记:04 Feasibility of Learning
- ubuntu 16.04系统下解决MySQL 5.7版本的root用户重置密码问题
- 初读";Thinking in Java";读书笔记之第六章 --- 访问权限控制
- LaTeX简历模板
- 字典和json 的区别 和转换
- CentOS7下启用网卡