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

讨厌啦,bfs忘了怎么打了,竟然用了记忆化搜索……

Posted by jhqwan at 2015-07-06 16:02:27 on Problem 1088
#include<algorithm>
#include<iostream>
#define fi cin
#define fo cout
  
using namespace std;
  
const int MAX = 101;
int n,m,f[MAX][MAX]={0},h[MAX][MAX],ans=0,dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
void idax(int, int);
 
main()
{
    ios::sync_with_stdio(false);
    fi >> n >> m;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            fi >> h[i][j];
          
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
        {
            idax(i, j);
            ans = max(ans, f[i][j]); 
        }
      
    fo << ans + 1;
}
  
void idax(int x, int y)
{
    if(f[x][y] > 0)
        return;
    for(int i = 0; i < 4; i ++)
    {
        int nx = x + dx[i], ny = y + dy[i];
        if(nx > 0 && nx <= n && ny > 0 && ny <= m && h[x][y] < h[nx][ny])
        {
            idax(nx, ny);
            f[x][y] = max(f[x][y], f[nx][ny] + 1);
        }
    }
}

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