| ||||||||||
| 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