백준 1103번 게임 ( C++ )

문제

https://www.acmicpc.net/problem/1103

 

해설

모든 경우의 수를 고려할 경우 (50*50)의 4제곱이 되기 때문에 dp를 이용해서 해결

 

코드

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int n,m,dp[54][54], ret;
char mp[54][54];
int dy[4] = {-1,0,1,0};
int dx[4] = {0,1,0,-1};
string line;
void go(int y, int x, int cnt){
  if(cnt > n*m){
    ret = -1;
    return;
  }
  if(ret == -1 || (dp[y][x] && dp[y][x] >= cnt)) return;
 
  dp[y][x] = cnt;
  int move = mp[y][x] - '0';
  for(int i=0;i<4;i++){
    int ny = y + move*dy[i];
    int nx = x + move*dx[i];
    if(ret == -1){
      return;
    }
    if(ny<0 || ny >= n || nx<0 || nx>=m ){
      ret = max(ret,cnt+1);
    }
    else if(mp[ny][nx] == 'H'){
      ret = max(ret,cnt+1);
    }
    else{
      go(ny,nx,cnt+1);
    }
  }
}
 
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
 
  cin >> n>>m;
  for(int i=0; i<n;i++){
    cin >> line;
    for(int j=0;j<m;j++){
      mp[i][j] = line[j];
    }
  }
 
  go(0,0,0);
 
  cout << ret;
  return 0;
}