[백준/C++] 17130 토끼가 정보섬에 올라온 이유

17130 토끼가 정보섬에 올라온 이유

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

17130번: 토끼가 정보섬에 올라온 이유

#include<bits/stdc++.h>

using namespace std;

int n, m, startY ,ans = 0;
string s;
int dp[1001][1001] = { 0, };
char _map[1001][1001];
bool check = false;

void move()
{
	for (int j = startY; j < m; ++j)
	{
		for (int i = 0; i < n; ++i)
		{
			if ('#' == _map[i][j])
				continue;
			if (i - 1 >= 0 && j - 1 >= 0 && dp[i - 1][j - 1] != -1)
				dp[i][j] = max(dp[i][j], dp[i - 1][j - 1]);
			if (j - 1 >= 0 && dp[i][j - 1] != -1)
				dp[i][j] = max(dp[i][j], dp[i][j - 1]);
			if (i + 1 < n && j - 1 >= 0 && dp[i + 1][j - 1] != -1)
				dp[i][j] = max(dp[i][j], dp[i + 1][j - 1]);
			
			if ('C' == _map[i][j] && dp[i][j] != -1)
				++dp[i][j];
			if ('O' == _map[i][j] && dp[i][j] != -1)
			{
				check = true;
				ans = max(ans, dp[i][j]);
			}

		}
	}
}

int main()
{
	memset(dp, -1, sizeof(dp));
	cin >> n >> m;
	for (int i = 0; i < n; ++i)
	{
		cin >> s;
		for (int j = 0; j < s.size(); ++j)
		{
			_map[i][j] = s[j];
			if ('R' == _map[i][j])
			{
				startY = j;
				dp[i][j] = 0;
			}
		}
	}
	move();
	if (check)
		cout << ans << "\\n";
	else
		cout << "-1" << "\\n";

	return 0;
}

• 토끼는 →, ↘, ↗ 방향으로만 이동 가능하다.
• 방금 토끼 한 마리가 정보섬 정문으로 들어왔다. → 이말의 뜻이 x는 0에서 시작한다는 것을 의미한다.
• dp를 사용해서 풀어야하는 문제, bfs를 통해서도 풀 수는 있을듯 하다