POJ 2329 (暴力+搜索bfs） - c++编程基础

Nearest number - 2

Time Limit: 5000MS		Memory Limit: 65536K
Total Submissions: 3943		Accepted: 1210

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

Sample Output

1 0 2
1 0 2
0 3 0

#include
  
   
#include
   
     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
    
     
 
      
      
     （借鉴大大的思路） 
     值得学习的是，对于矩阵的逆时针菱形搜索，思考了很长时间都没有想清楚。 
     自己可以试一下顺时针，一样的道理哦。





 
     int dx[]={1,1,-1,-1},cx[]={-1,0,1,0};
 int dy[]={-1,1,1,-1},cy[]={0,-1,0,1}; 
     主要是这两对数组，用的很是巧妙！