POJ 2329 Nearest number - 2
题意：解题过程：AC代码：
POJ 2329 Nearest number - 2
题目传送门
题意：
你有一个n*n矩阵，每个点有一个数字，可能是0~1e9的任意一个数字，现在要求你对这个矩阵进行修改，对于所有的为0的数字，要求寻找到这个点曼哈顿距离最小的非0的一个数，并把这个点改为那个数的值，如果有多个数到这个点的曼哈顿距离都是最小的，那么这个点还是为0。要求输出修改之后的矩阵。
解题过程：
我们可以对于每个点进行一次BFS，遍历每个曼哈顿距离为一定值的点，判断这些点是否为0，并且记录不为零的点的个数。如果个数恰好为1，那么直接输出这个点的值，如果个数为0，那么加大曼哈顿距离的值，继续搜索，如果大于2，那么直接输出0。
AC代码：
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <vector>
#include <cstdlib>
#include <cstring>
using namespace std;
int a[
205][
205];
int b[
205][
205];
int vis[
205][
205];
int dir[
4][
2]={{
1,
0},{
0,
1},{-
1,
0},{
0,-
1}};
int n;
int c[
405];
int d[
405];
struct Node
{
int x,y;
};
void FO() {
freopen(
"data.txt",
"r",stdin);
freopen(
"good.txt",
"w",stdout);
}
void bfs(
int x,
int y)
{
Node Q[
40005];
int rear=
0,front=
0;
int flag=
0,level=
9999999;
Node term;
term.x=x;
term.y=y;
Q[rear++]=term;
vis[x][y]=
1;
while(rear!=front&&flag!=-
1)
{
Node temp=Q[front++];
if(level<=vis[temp.x][temp.y])
break;
for(
int i=
0;i<
4;i++)
{
int xx=temp.x+dir[i][
0];
int yy=temp.y+dir[i][
1];
if(xx<
0||xx>n-
1||yy<
0||yy>n-
1||vis[xx][yy])
continue;
vis[xx][yy]=vis[temp.x][temp.y]+
1;
if(a[xx][yy]!=
0)
{
if(!flag)
{
flag=a[xx][yy];
level=vis[xx][yy];
}
else
{
flag=-
1;
break;
}
}
else
{
Node item;
item.x=xx;
item.y=yy;
Q[rear++]=item;
}
}
}
if(flag>
0)
b[x][y]=flag;
}
void init()
{
memset(vis,
0,
sizeof(vis));
memset(c,
0,
sizeof(c));
}
int main()
{
while(
scanf(
"%d",&n)!=EOF)
{
for(
int i=
0;i<n;i++)
for(
int j=
0;j<n;j++)
{
scanf(
"%d",&a[i][j]);b[i][j]=a[i][j];}
for(
int i=
0;i<n;i++)
for(
int j=
0;j<n;j++)
{
if(a[i][j]==
0)
{
init();
bfs(i,j);
}
}
for(
int i=
0;i<n;i++)
{
for(
int j=
0;j<n;j++)
{
if(j!=n-
1)
printf(
"%d ",b[i][j]);
else
printf(
"%d",b[i][j]);
}
printf(
"\n");
}
}
return 0;
}
本人蒟蒻OIer一枚，欢迎加QQ：840776708一起学习蛤。
转载于:https://www.cnblogs.com/Apocrypha/p/9433670.html
相关资源：JAVA上百实例源码以及开源项目
