BOJ 1103 : 게임

무서운 정답률과 달리 문제는 상당히 쉽습니다. 

 

코드도 직관적입니다. 바로 코드를 보겠습니다.

#include<bits/stdc++.h>
using namespace std;
int N, M, maxx=-1, dp[51][51];
bool finished=false, visited[51][51];
char arr[51][51];
static int dx[4]={-1, 0, 1, 0}, dy[4]={0, -1, 0, 1};
int dfs(int x, int y){
	if(finished) return -1;
	if(visited[x][y]){
		finished=true;
		return -1;
	}
	if(dp[x][y]>0) return dp[x][y];
	if(arr[x][y]=='H') return dp[x][y]=0;
	dp[x][y]=1;
	for(int i=0;i<4;i++){
		int nx=x+dx[i]*(arr[x][y]-'0');
		int ny=y+dy[i]*(arr[x][y]-'0');
		if(nx<0 or ny<0 or nx>=N or ny>=M) continue;
		visited[x][y]=true;
		dp[x][y]=max(dp[x][y], 1+dfs(nx, ny));
	} // step: -1처리 위함
	visited[x][y]=false; // 근데 이 처리가 맞음?  
	return dp[x][y];
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> N >> M;
	for(int i=0;i<N;i++){
		string s;
		cin >> s;
		for(int j=0;j<s.length();j++){
			arr[i][j]=s[j];
		}
	}
	dfs(0, 0);
	if(finished) cout << "-1";
	else cout << dp[0][0];
}

 

여담이지만, dx, dy배열에 arr[x][y]를 곱하는 것이 뭔가 벡터에다가 스칼라 곱하는거랑 비슷해서 재밌었네요.

골드II에 있을 문제는 아닌 것 같습니다.

 

아, 제 백준 아이디를 이제까지 써놓질 않았네요.

wifi0725가 제 아이디입니다. 감사합니다.

https://solved.ac/profile/wifi0725 

solved.ac