poj 1088ダイナミックプランニング

単純なダイナミックプランニング.
記憶化探索を用いて,各点について上下左右の解を行い,この点の最大値は必ず4方向の中から最大の+1である.

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

const int maxn=105;
int map[maxn][maxn];
int dp[maxn][maxn];
int dx[]={-1,0,1,0},dy[]={0,-1,0,1};

int dfs(int x,int y){
	if(dp[x][y])return dp[x][y];
	for(int i=0;i<4;i++){
		int xx=x+dx[i],yy=y+dy[i];
		if(map[xx][yy]!=-1&&map[xx][yy]<map[x][y])dp[x][y]=max(dp[x][y],dfs(xx,yy)+1);
	}
	return dp[x][y];
}

int main(){
	int r,c;
	while(scanf("%d%d",&r,&c)==2){
		memset(map,-1,sizeof(map));
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=r;i++)for(int j=1;j<=c;j++)scanf("%d",&map[i][j]);
		int ans=0;
		for(int i=1;i<=r;i++){
			for(int j=1;j<=c;j++){
				ans=max(ans,dfs(i,j));
			}
		}
		printf("%d
",ans+1);
	}
}