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

小白记忆话搜索练习

Posted by xsjlmzs at 2018-03-28 16:51:57 on Problem 1088
开始以为广搜一下就可一乐,后来发现自己太naive了。。。
优化后的代码,大神轻喷。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<utility>
using namespace std;
int arr[105][105];
int dp[105][105]={-1};
int n,m;
int mx(int a,int b,int c,int d)
{
    int temp=0;
    if(a>temp)
        temp=a;
    if(b>temp)
        temp=b;
    if(c>temp)
        temp=c;
    if(d>temp)
        temp=d;
    return temp;
}
int res(int x,int y)
{
    int a=0,b=0,c=0,d=0;
    if(dp[x][y]>0)
        return dp[x][y];
    if(x>n||x<=0||y<=0||y>m)
        return 0;
    else if(arr[x-1][y]>=arr[x][y]&&arr[x+1][y]>=arr[x][y]&&arr[x][y-1]>=arr[x][y]&&arr[x][y+1]>=arr[x][y])
        return dp[x][y]=0;
    else
    {
        if(arr[x+1][y]<arr[x][y])
            a=res(x+1,y);
        if(arr[x-1][y]<arr[x][y])
            b=res(x-1,y);
        if(arr[x][y+1]<arr[x][y])
            c=res(x,y+1);
        if(arr[x][y-1]<arr[x][y])
            d=res(x,y-1);
    }
     return dp[x][y]=mx(a,b,c,d)+1;
}
int main(void)
{
    while(scanf("%d%d",&n,&m)==2)
    {
        memset(dp,0,sizeof(dp));
        memset(arr,0x3f,sizeof(arr));
        for(int i=1; i<=n; ++i)
        {
            for(int j=1; j<=m; ++j)
                scanf("%d",&arr[i][j]);
        }
        int mn=-99;
        for(int i=1; i<=n; ++i)
        {
            for(int j=1; j<=m; ++j)
            {
                int temp=res(i,j);
                mn=max(mn,temp);
            }
        }
        printf("%d\n",mn+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