POJ 1088スキー(記憶化DP)問題解

//      
/***
*
*                          ，            
*        。               。
***/

#include 
#include 
#define MAX 123456
using namespace std;
//     +         dp
int R,C,map[105][105],step[105][105];
int xx[]={-1,0,1,0};
int yy[]={0,1,0,-1};
int dfs(int x,int y){
    if(step[x][y]!=0){//  step[x][y]               ，       ，         
        return step[x][y];
    }
    int ans=1;
    for(int i=0;i<4;i++){//             
        int tmpx=x+xx[i];
        int tmpy=y+yy[i];
        if(tmpx>=0&&tmpx=0&&tmpymap[tmpx][tmpy]){//                
                int tmp=dfs(tmpx,tmpy);//      ，          
                if(tmp>=ans){
                    ans=tmp+1;
                }
            }
        }
    }
    step[x][y]=ans;//          
    return step[x][y];
}

int main(){
    while(~scanf("%d %d",&R,&C)){
        for(int x=0;x

//      
/***
*
*                          ，            
*        。               。
***/

#include 
#include 
#define MAX 123456
using namespace std;
//     +         dp
int R,C,map[105][105],step[105][105];
int xx[]={-1,0,1,0};
int yy[]={0,1,0,-1};
int dfs(int x,int y){
    if(step[x][y]!=0){//  step[x][y]               ，       ，         
        return step[x][y];
    }
    int ans=1;
    for(int i=0;i<4;i++){//             
        int tmpx=x+xx[i];
        int tmpy=y+yy[i];
        if(tmpx>=0&&tmpx=0&&tmpymap[tmpx][tmpy]){//                
                int tmp=dfs(tmpx,tmpy);//      ，          
                if(tmp>=ans){
                    ans=tmp+1;
                }
            }
        }
    }
    step[x][y]=ans;//          
    return step[x][y];
}

int main(){
    while(~scanf("%d %d",&R,&C)){
        for(int x=0;x

/***
*                  ，         
*          
*       :         ，       ，       
*           。
***/
#include
#include
#include
#define MAX 123456
using namespace std;
typedef struct node{
    int x;
    int y;
    int w;
}Node;


int R,C,map[105][105],step[105][105]//             ;
int maxx;
int xx[]={-1,0,1,0};
int yy[]={0,1,0,-1};
void deal(Node p){
    maxx=0;
    queueQue;
    Que.push(p);
    Node t;
    while(!Que.empty()){
        p=Que.front();
        Que.pop();
        for(int i=0;i<4;i++){
            t.x=p.x+xx[i];
            t.y=p.y+yy[i];
            t.w=map[t.x][t.y];
            if(t.x>=0&&t.x=0&&t.yt.w){//    
                if(step[p.x][p.y]>=step[t.x][t.y]){//    
                    step[t.x][t.y]=step[p.x][p.y]+1;
                    if(maxx