80分 #1WA #2TLE求大佬救火
查看原帖
80分 #1WA #2TLE求大佬救火
246799
yyj051101楼主2021/10/9 22:29

#1WA #2TLE求大佬救火QWQ

dis[x][y]是这个点的最大距离,Pmap是边界判断

#include <iostream>
#include <math.h>

using namespace std;

const int MAXX = 110;
int map[MAXX][MAXX] , dis[MAXX][MAXX] , ans , R , C;
bool Pmap[MAXX][MAXX];

inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}

int dp(int x , int y){
	if(dis[x][y] ==! 0){
		return dis[x][y];
	}else{
		dis[x][y] = 1;
	}
	
	if(map[x][y] > map[x + 1][y] && Pmap[x + 1][y]){
			dis[x][y] = max(dis[x][y] , dp(x + 1 , y) + 1);
	}
	if(map[x][y] > map[x - 1][y] && Pmap[x - 1][y]){
			dis[x][y] = max(dis[x][y] , dp(x - 1 , y) + 1);
	}
	if(map[x][y] > map[x][y + 1] && Pmap[x][y + 1]){
			dis[x][y] = max(dis[x][y] , dp(x , y + 1) + 1);
	}
	if(map[x][y] > map[x][y - 1] && Pmap[x][y - 1]){
			dis[x][y] = max(dis[x][y] , dp(x , y - 1) + 1); 
	}
	
	return dis[x][y];
}

int main() {
//	freopen("luoguP1434.in" , "r" , stdin);
	R = read();
	C = read();
	for(int i = 1; i <= R; i++){
		for(int j = 1; j <= C; j++){
			map[i][j] = read();
			Pmap[i][j] = 1;
			dis[i][j] = 0;
		}
	}
	for(int i = 0; i <= R; i++){
		Pmap[0][i] = 0;
		Pmap[C + 1][i] = 0;
	}
	for(int i = 0; i <= C; i++){
		Pmap[i][0] = 0;
		Pmap[i][R + 1] = 0;
	}
	for(int i = 1; i <= R; i++){
		for(int j = 1; j <= C; j++){
			ans = max(ans , dp(i , j));
		}
	}
	
	cout << ans;
	
	return 0;
}
2021/10/9 22:29
加载中...