POJ2329总结

Nearest number – 2

题目来源

Description

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

A distance between two elements A_ij and A_pq 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 N² integers, representing the matrix row-by-row.

Output

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

Sample Input

3
0 0 0
1 0 2
0 3 0

Sample Output

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");
	}
}