C++

재귀함수

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int N,M,S,T;

int map_[110][40],dt[40][110],result=110;

int serch(int room,int day){

   if(dt[room][day]!=-1)

      return dt[room][day];

   if(day==T)

      return 0;

   int min_=110,cnt=0;

   for(int i=1;i<=M;i++){

      if(map_[day+1][i]==1){

         int a=serch(i,day+1);

         if(a==-1)

            return -1;

         if(i==room){

            min_=min(min_,a);

         }else{

            min_=min(min_,a+1);

         }

         cnt++;

      }

   }

   if(cnt==0||min_==-1)

      return -1;

   return dt[room][day] = min_;

}

int main()

{

   memset(dt,-1,sizeof(dt));

    scanf("%d %d",&N,&M);

    for(int i=1;i<=N;i++){

      for(int j=1;j<=M;j++){

         char a;

         scanf(" %c",&a);

         map_[i][j]=(a=='X')? 0:1;

      }

    }

    scanf("%d %d",&S,&T);

    T--;

    for(int i=1;i<=M;i++){

      if(map_[S][i]==1)

         result=min(result,serch(i,S));

    }

    if(result==110)

      result=-1;

    printf("%d",result);

    return 0;

}

Bottom-up

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int N,M,S,T;

int map_[110][40];

int main()

{

    scanf("%d %d",&N,&M);

    for(int i=1;i<=N;i++){

      for(int j=1;j<=M;j++){

         char a;

         scanf(" %c",&a);

         map_[i][j]=(a=='X')? 0:1+map_[i-1][j];

      }

    }

    scanf("%d %d",&S,&T);

    T--;

    int t=T,cnt=0;

    while(t>=S){

        int max_=-1;

        cnt++;

        for(int i=1;i<=M;i++){

            max_=max(max_,map_[t][i]);

        }

        if(max_<1){

            printf("-1");

            return 0;

        }

        t-=max_;

    }

    printf("%d",cnt-1);

 

    return 0;

}