[백준 1520 - 골드 4] 내리막 길.cpp

C++/CodingTest

통계전공 개발자 2022. 5. 6. 22:42

1520번: 내리막 길

여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으

www.acmicpc.net

	#define _CRT_SECURE_NO_WARNINGS
	#include <stdio.h>

	using namespace std;

	const int MAX = 500;

	struct Pos
	{
	int row, col;
	};

	int N, M;
	int map[MAX][MAX];
	int chk[MAX][MAX];

	bool isVaild(Pos cur, Pos next)
	{
	if (next.row < 0 \|\| next.row >= M \|\| next.col < 0 \|\| next.col >= N)
	{
	return false;
	}

	if (map[next.row][next.col] >= map[cur.row][cur.col])
	{
	return false;
	}

	return true;
	}

	bool isArrive(Pos pos)
	{
	if (pos.row == M - 1 && pos.col == N - 1)
	{
	return true;
	}

	return false;
	}

	void Input()
	{
	//freopen("input.txt", "r", stdin);

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

	for (int r = 0; r < M; r++)
	{
	for (int c = 0; c < N; c++)
	{
	scanf("%d", &map[r][c]);
	chk[r][c] = -1;
	}
	}
	}


	void DFS(Pos cur)
	{
	static int dr[4] = { 1, -1, 0, 0 };
	static int dc[4] = { 0, 0, 1, -1 };

	if (chk[cur.row][cur.col] == -1)
	{
	chk[cur.row][cur.col] = 0;
	}
	if (isArrive(cur) == true)
	{
	chk[cur.row][cur.col]++;
	return;
	}

	for (int i = 0; i < 4; i++)
	{
	Pos next = { cur.row + dr[i], cur.col + dc[i] };

	if (isVaild(cur, next) == true)
	{

	if (chk[next.row][next.col] == -1)
	{
	DFS(next);
	}

	chk[cur.row][cur.col] += chk[next.row][next.col];

	}
	}
	}

	void Sol()
	{
	Pos begin = { 0, 0 };

	DFS(begin);

	printf("%d", chk[0][0]);
	}
	int main()
	{
	Input();
	Sol();

	return 0;
	}