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 ≤ 1000000Input
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.Sample Input
3 0 0 0 1 0 2 0 3 0Sample Output
1 0 2 1 0 2 0 3 0 #include<iostream> #include<cstdio> using namespace std; int n; int matri[210][210]; int dx[]={1,1,-1,-1},cx[]={-1,0,1,0}; int dy[]={-1,1,1,-1},cy[]={0,-1,0,1}; bool in_matrix(int x,int y) { if(x<0||x>=n) return false; if(y<0||y>=n) return false; return true; } int bfs(int x,int y,int k) { if(k>n) return 0; //n*n matrix搜索K次，自己能够特值来理解 if(matri[x][y]||n==1) return matri[x][y]; //数不为0，或仅仅有一个数（即 1*1 矩阵），就输出 int xx,yy,X,Y; int i,j; int cnt=0,die=0; for(i=0;i<4;i++) //对于菱形4条边的搜索，这里是以每边K个数字来写。 { xx=x+k*cx[i]; yy=y+k*cy[i]; for(j=k;j--;) //相当于for(j=0;j<k;j++),一边k个数，所以搜索k次 { if(in_matrix(xx,yy)&&matri[xx][yy]) { if(cnt==1) { die=1; break; } X=xx; Y=yy; cnt++; } xx+=dx[i]; yy+=dy[i]; } if(die) break; } if(cnt==0) return bfs(x,y,k+1); else if(die) return 0; else return matri[X][Y]; } int main() { scanf("%d",&n); for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) scanf("%d",&matri[i][j]); for(int i = 0; i < n; ++i,printf("\n")) for(int j = 0; j < n; ++j) printf("%d ",bfs(i,j,1)); return 0; }（借鉴大大的思路）
值得学习的是，对于矩阵的逆时针菱形搜索。思考了非常长时间都没有想清楚。
自己能够试一下顺时针，一样的道理哦。
int dx[]={1,1,-1,-1},cx[]={-1,0,1,0}; int dy[]={-1,1,1,-1},cy[]={0,-1,0,1};
主要是这两对数组。用的非常是巧妙！
版权声明：本文博客原创文章。博客，未经同意，不得转载。
转载于:https://www.cnblogs.com/bhlsheji/p/4661493.html
