POJ 2329 (暴力+搜索bfs）
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 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.Sample Input
3
0 0 0
1 0 2
0 3 0
Sample Output
1 0 2
1 0 2
0 3 0
#include
#includeusing 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};
主要是这两对数组，用的很是巧妙！
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！