记忆化搜索,求助一段代码有无结果不同
查看原帖
记忆化搜索,求助一段代码有无结果不同
427110
Logiking楼主2021/5/8 19:37
#include<iostream>
using namespace std;
int r,c;
int sear[201][201];
int dp[201][201];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
//int ans = 1;
int m;
int sousuo(int x,int y){
	if(dp[x][y])return dp[x][y];
    /*为什么多了这段代码5和7测试点就WA呢?
    if(sear[x][y] == 1){
		dp[x][y] = 1;
		return dp[x][y];
	};
    */
	int m1 = 0;
	int i;
	for(i = 0; i < 4; ++i){
		int x1 = x + dx[i];
		int y1 = y + dy[i];
		if(x1 >= 1 && y1 >= 1 && x1 <= r && y1 <= c && sear[x1][y1] < sear[x][y]){
			m1 = max(m1,sousuo(x1,y1));
		}
}
		m1++;
		dp[x][y] = m1;
	return dp[x][y];
}
int main(){
	cin >> r >> c;
	int i,j;
	for(i=1; i <= r; ++i){
		for(j = 1; j <= c ;++j){
			cin >> sear[i][j];
		}
}			
	for(i=1; i <= r; ++i){
		for(j = 1; j <= c ;++j){
			m = max(m,sousuo(i,j));
		}
}	
	cout << m;
//	cout << "-----------" << endl;
//	for(i=1; i <= r; ++i){
//		for(j = 1; j <= c ;++j)
//			cout << dp[i][j] << " ";
//		cout << endl;
//}
	return 0;
}
2021/5/8 19:37
加载中...