Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

G++ RE C++ 250 ms 应该算是 n^4 的算法吧 逆时针转着圈的找..... 水过....顺便贴个50行代码. 不喜勿喷

Posted by ysymi at 2013-02-13 01:14:20 on Problem 2329 and last updated at 2013-02-13 01:17:31
# 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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator