Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
G++ RE C++ 250 ms 应该算是 n^4 的算法吧 逆时针转着圈的找..... 水过....顺便贴个50行代码. 不喜勿喷# include <cstdio> int n, res[210][210]; int dx[4] = {1,1,-1,-1}, cx[4] = {-1,0,1,0}; int dy[4] = {-1,1,1,-1}, cy[4] = {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; if (res[x][y] || n == 1) return res[x][y]; int cnt = 0, ok = 1, X, Y; for(int i = 0; i < 4 && ok; ++i) { int xx = x+k*cx[i], yy = y+k*cy[i], kk = k; for(int kk = k; kk --; ) { if (res[xx][yy]&& in_matrix(xx,yy)) { X = xx; Y = yy; ++cnt; if (cnt > 1) break; } xx += dx[i]; yy += dy[i]; } if (cnt > 1) ok = 0; } if (cnt == 1) return res[X][Y]; else return cnt == 0 ? bfs(x,y,k+1) : 0 ; } int main() { scanf("%d",&n); for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) scanf("%d",&res[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; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator