关于dfs的MLE问题

苏黎世 @ 2020-10-22 19:53:02

#include<cstdio>
#include<cmath>
#define intt register int
using namespace std;
//MLE ???
int m[105][105], r, c, ans, vis[105][105];
int d[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
inline int max(int x, int y)
{
    return x > y ? x : y;
}
inline void dfs(int x, int y, int sum)
{
    vis[x][y] = vis[x][y] > sum ? vis[x][y] : sum;
    ans = ans > sum ? ans : sum;
    int _x, _y;
    for(intt i = 0;i < 4; ++i)
    {
        _x = x + d[i][0]; _y = y + d[i][1];
        if(_x >= 1 and _x <= r and _y >= 1 and _y <= c and vis[_x][_y] <= vis[x][y] and m[x][y] >= m[_x][_y])
          dfs(_x, _y, sum + 1);
    }
}

int main()
{
    scanf("%d%d", &r, &c);
    for(intt i = 1;i <= r; ++i)
      for(intt j = 1;j <= c; ++j)
        scanf("%d", &m[i][j]);

    for(intt i = 1;i <= r; ++i)
      for(intt j = 1;j <= c; ++j)
        dfs(i, j, 1);

    printf("%d", ans);
    return 0;
}

by wocaicai @ 2020-10-22 20:18:49

@苏黎世 看完了，我来说说问题qwq

您的vis指的应该是到那里走了多少步，但是我一看就觉得这东西感觉没啥用啊，要剪枝的话应该是记录从这个点出发能走多少步，这样下次有点来就直接取这里的信息就好了，这样才是有效的剪枝qwq

具体实现看代码吧，刚写的qwq（顺便进了一波前10最优解qwq）

dfs不是不行，就是一定要剪枝

#include<bits/stdc++.h>
using namespace std ;
#define kkk signed main
inline int read(){
    int ans = 0 , f = 1 ; char ch = getchar() ;
    while ( !isdigit(ch)) {  if( ch == '-' )  f = -1 ; ch = getchar() ; }
    while ( isdigit(ch) ) ans =  (ans * 10 ) + (ch ^ '0' ), ch = getchar() ;
    return ans * f ;
}
int dx[4] = {-1 , 1 , 0 , 0 } ; 
int dy[4] = {0 , 0 , -1 , 1 } ; 
int n , m , ans ; 
int heigt[110][110] , can[110][110] , vis[110][110]; 
int dfs(int x , int y){
    if(vis[x][y]) return can[x][y] ; 
    vis[x][y] = 1 ; 
    for(int i = 0 ; i < 4 ; i++){
        int tx = x + dx[i] ; 
        int ty = y + dy[i] ;
        if(tx <= n && tx >= 1 && ty <= m && ty >= 1 && heigt[x][y] > heigt[tx][ty])
            can[x][y] = max(can[x][y] , dfs(tx , ty) + 1) ;  
    }
    return can[x][y] ; 
}
kkk(){
    n = read() , m = read() ; 
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= m ; ++j)
            heigt[i][j] = read() , can[i][j] = 1 ; 
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= m ; ++j)
            ans = max(ans , dfs(i , j)); 
    printf("%lld" , ans) ; 
}

by LordLaffey @ 2020-10-23 14:31:43

楼上的做法说是剪枝不如说是记忆化吧