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

DFS居然也能水过,这数据。。。

Posted by 201213137089 at 2014-07-28 15:28:12 on Problem 1088
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int N,M,ans,maps[105][105];
int step[105][105];

void dfs(int x,int y,int coun)
{

    if(ans<coun)
        ans = coun;
    if(x<=0||x>N||y<=0||y>M)
        return ;
    if(step[x][y]>=coun)
        return ;
    else step[x][y] = coun;
    if(x-1>0&&maps[x-1][y]<maps[x][y])
    {
        coun ++;
        dfs(x-1,y,coun);
        coun--;
    }
    if(x+1<=N&&maps[x+1][y]<maps[x][y])
    {
        coun++;
        dfs(x+1,y,coun);
        coun--;
    }
    if(y-1>0&&maps[x][y-1]<maps[x][y])
    {
        coun++;
        dfs(x,y-1,coun);
        coun--;
    }
    if(y+1<=M&&maps[x][y+1]<maps[x][y])
    {
        coun++;
        dfs(x,y+1,coun);
        coun--;
    }

}
int main()
{
    int maxs,startx,starty;
    while(~scanf("%d%d",&N,&M))
    {
        maxs = 0;ans  = 0;
        memset(step,0,sizeof(step));
        for(int i =1;i<=N;i++)
            for(int j =1;j<=M;j++)
            {
                scanf("%d",&maps[i][j]);

            }
        for(int i =1;i<=N;i++)
        {
            maxs = 0;
            for(int j =1;j<=M;j++)
            {
                if(maxs<maps[i][j])
                {
                    startx = i;
                    starty = j;
                    maxs= maps[i][j];
                }
            }
                dfs(startx,starty,1);
        }

        cout<<ans<<endl;
    }
    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