# POJ2329总结

## Nearest number – 2

### Description

Input is the matrix A of N by N non-negative integers.

A distance between two elements Aij and Apq is defined as |i − p| + |j − q|.

Your program must replace each zero element in the matrix with the nearest non-zero one. If there are two or more nearest non-zeroes, the zero must be left in place.
Constraints
1 ≤ N ≤ 200, 0 ≤ Ai ≤ 1000000

### Input

Input contains the number N followed by N2 integers, representing the matrix row-by-row.

### Output

Output must contain N2 integers, representing the modified matrix row-by-row.

```3
0 0 0
1 0 2
0 3 0
```

```1 0 2
1 0 2
0 3 0```

### 思路

``````const int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
//选择一个方向上的顶点
const int step[4][2]={{1,-1},{1,1},{-1,1},{-1,-1}};//这个顶点对应的步长。``````
``````#include<stdio.h>
#include<string.h>

const int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
const int step[4][2]={{1,-1},{1,1},{-1,1},{-1,-1}};

int n;
int matrix[210][210];

int check(int x,int y){
if (x>=0&&x<n&&y>=0&&y<n){
return 1;
}else return 0;
}

int bfs(int x,int y,int len){
if (len>n) return 0;
if (matrix[x][y]!=0||n==1){
return matrix[x][y];
}
int xx,yy,X,Y;
int cnt=0,die=0;
for (int i=0;i<4;i++){
xx=x+len*dir[i][0];
yy=y+len*dir[i][1];
for(int j=0;j<len;j++){
if(check(xx,yy)&&matrix[xx][yy]){
if (cnt==1){
die=1;
break;
}
X=xx;
Y=yy;
cnt++;
}
xx+=step[i][0];
yy+=step[i][1];
}
if (die){
break;
}

}
if (cnt==0){
return bfs(x,y,len+1);
} else if (die){
return 0;
}else {
return matrix[X][Y];
}
}

int main(){
scanf("%d",&n);
for (int i=0;i<n;i++){
for (int j=0;j<n;j++){
scanf("%d",&matrix[i][j]);
}
}

for (int i=0;i<n;i++){
for (int j=0;j<n;j++){
printf("%d ",bfs(i,j,1));
}
printf("\n");
}
}``````