【求助】求问这两种记忆化搜索方法的区别
查看原帖
【求助】求问这两种记忆化搜索方法的区别
202490
me528963楼主2020/10/15 23:49

rt,下面是蒟蒻写的两种记忆化搜索的代码: code1:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 105;
ll rec[N][N];
int r,n;
ll f[N][N];
int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};
ll findroute(int i,int j){
    if(f[i][j])
        return f[i][j];
    f[i][j] = 1;
    for (int t = 0; t < 4;t++){
        int x = i + dx[t], y = j + dy[t];
        if((x>0 && y>0 && x<=r && y<=n) && rec[x][y]<rec[i][j]){
            f[i][j]=max(f[i][j],(findroute(x, y)+1));
        }
    }
    return f[i][j];
}
int main(){
    memset(f, 0, sizeof(f));
    cin >> r >> n;
    for (int i = 1; i <= r;i++){
        for (int j = 1; j <= n;j++){
            cin >> rec[i][j];
        }
    }
    ll ans = 0;
    for (int i = 1; i <= r; i++){
        for (int j = 1; j <= n;j++){
            ans = max(ans, findroute(i, j));
        }
    }
    cout << ans << endl;
}

code2(只有findroute代码不同)

ll findroute(int i,int j){
    if(f[i][j])
        return f[i][j];    
    if(rec[i][j]==1){
		f[i][j]+=1;
		return f[i][j];
	 }
  	 ll ans = 0;
    for (int t = 0; t < 4;t++){
        int x = i + dx[t], y = j + dy[t];
        if((x>0 && y>0 && x<=r && y<=n) && rec[x][y]<rec[i][j]){
            ans=max(ans,(findroute(x, y)+rec[i][j]-rec[x][y]));
        }
    }
    f[i][j] = ans;
    return f[i][j];
}

code1是参考讨论区里的大佬的回答修改的,code2是自己最初写的,最后code1能够AC,而code2只能过三个点,请问这两种的差别在哪里,先谢谢回答的大佬了

2020/10/15 23:49
加载中...