求助!!WA一个点P7
查看原帖
求助!!WA一个点P7
464195
故人听雨楼主2022/4/2 01:19
#include <bits/stdc++.h>
using namespace std;
const long long maxn = 999999999;
int R,C;
int graph[102][102];
int least[102][102];
bool b[102][102];
int minn = 0;
int dir[5][2] = {
	{0,0},{-1,0},{0,-1},{0,1},{1,0}
};
bool check(int x,int y){
	for(register int i(1);i <= 4;i++){
		if(x + dir[i][0] > R || y + dir[i][1] > C
		|| x + dir[i][0] < 1 || y + dir[i][1] < 1){continue;}
		else if(!b[x + dir[i][0]][y + dir[i][1]] 
		&& graph[x + dir[i][0]][y + dir[i][1]] < graph[x][y]){return 0;}
	}
	return 1;
}
int dfs(int x,int y,int sum){
	if(check(x,y)){
		minn = max(minn,sum);
		least[x][y] = 1;
		return 1;
	}
	int pre = 0;
	for(register int i(1);i <= 4;i++){
		if(!b[x + dir[i][0]][y + dir[i][1]] 
			&& graph[x + dir[i][0]][y + dir[i][1]] < graph[x][y]
			&& x + dir[i][0] <= R && y + dir[i][1] <= C
			&& x + dir[i][0] >= 1 && y + dir[i][1] >= 1){
			if(least[x + dir[i][0]][y + dir[i][1]] != 0){
					if(sum + least[x + dir[i][0]][y + dir[i][1]] <= minn){continue;}
			}
			b[x + dir[i][0]][y + dir[i][1]] = 1;
			pre = dfs(x + dir[i][0],y + dir[i][1],sum + 1)+1;
			least[x][y] = max(least[x][y],pre);
			b[x + dir[i][0]][y + dir[i][1]] = 0;
		}
	}
	return pre;
}
int main()
{
	cin >> R >> C;
	for(register int i(1);i<=R;i++)
	for(register int j(1);j<=C;j++){
		cin >> graph[i][j];
	}
	for(register int i(1);i<=R;i++)
	for(register int j(1);j<=C;j++){
		b[i][j] = 1;
		dfs(i,j,0);
		b[i][j] = 0;
	}
	cout << minn+1;
	return 0;
}

2022/4/2 01:19
加载中...