1088:滑雪 10285:Longest Run on a Snowboard

問題文

POJ
http://poj.org/problem?id=1088

UVa
http://uva.onlinejudge.org/external/102/10285.html

縦r,横cのグリッドが与えられる。
上下左右で、数字が現在のセルより小さいセルにのみ移動可能。
移動できる最長経路の長さを求めよ。

メモ化再帰した。

POJ

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int grid[101][101],r,c;
bool visit[101][101];
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int dp[101][101];

int rec(int x,int y){
	
	if(dp[y][x]>0)return dp[y][x];
	
	int res=0;
	
	visit[y][x]=true;
	
	for(int i=0;i<4;i++){
		int nx=x+dx[i],ny=y+dy[i];
		if(nx<0 || ny<0 || c<=nx ||r<=ny)continue;
		if(visit[ny][nx] || grid[y][x]<=grid[ny][nx])continue;
		res=max(res,rec(nx,ny));
	}
	
	visit[y][x]=false;
	
	return dp[y][x]=res+1;
}


int main(void){
	
	cin >> r >> c;
	
	for(int i=0;i<r;i++){
		for(int j=0;j<c;j++){
			cin >> grid[i][j];
		}
	}
	
	int ans=0;
	for(int i=0;i<r;i++){
		for(int j=0;j<c;j++){
			fill(visit[0],visit[101],false);
			ans=max(ans,rec(j,i));
		}
	}
		
	cout << ans << endl;
	
	return 0;
}

UVa

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
 
using namespace std;
 
int grid[101][101],r,c;
bool visit[101][101];
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int dp[101][101];
 
int rec(int x,int y){
   
  if(dp[y][x]>0)return dp[y][x];
   
  int res=0;
   
  visit[y][x]=true;
   
  for(int i=0;i<4;i++){
    int nx=x+dx[i],ny=y+dy[i];
    if(nx<0 || ny<0 || c<=nx ||r<=ny)continue;
    if(visit[ny][nx] || grid[y][x]<=grid[ny][nx])continue;
    res=max(res,rec(nx,ny));
  }
   
  visit[y][x]=false;
   
  return dp[y][x]=res+1;
}
 
 
int main(void){
   
  int n;
  cin >> n;
  while(n--){
    string name;
    cin >> name;
    cin >> r >> c;
     
    fill(dp[0],dp[101],0);
 
    for(int i=0;i<r;i++){
      for(int j=0;j<c;j++){
        cin >> grid[i][j];
      }
    }
     
    int ans=0;
    for(int i=0;i<r;i++){
      for(int j=0;j<c;j++){
        fill(visit[0],visit[101],false);
        ans=max(ans,rec(j,i));
      }
    }
     
    cout << name << ": " << ans << endl;
  }
  return 0;
}