[Brute Force - 재귀] 두 동전

 

예제 입력 1

1 2

oo

예제 출력 1

1

예제 입력 2

6 2

.#

.#

.#

o#

o#

##

예제 출력 2

4

예제 입력 3

6 2

..

..

..

o#

o#

##

예제 출력 3

3

예제 입력 4

5 3

###

.o.

###

.o.

###

예제 출력 4

-1

예제 입력 5

5 3

###

.o.

#.#

.o.

###

예제 출력 5

3

 

 

 

- 재귀에서 return 값 반환하는거 연습해보기.

 

#include <stdio.h>

#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX_SIZE (20)

#define MAX_VALUE (2147483647)

char map[MAX_SIZE][MAX_SIZE];

int R, C;
int result = -1;

int dR[4] = { -1, 1, 0, 0 };
int dC[4] = { 0, 0, -1, 1 };

bool visited1[MAX_SIZE][MAX_SIZE];
bool visited2[MAX_SIZE][MAX_SIZE];

class Point
{
public:
	int r, c;
	
	Point()
	{
	}

	Point(int r, int c) : r(r), c(c)
	{
		Point();
	} 

	bool isInBoundary()
	{
		return (r >= 0) && (r < R) && (c >= 0) && (c < C);
	}
};

int go(int cnt, Point coin1, Point coin2)
{
	// 종료조건
	// 1) cnt == 11
	// 2) 두 동전 모두 떨어진 경우
	// 3) 정답 찾은 경우 = 두 동전 중에서 하나만 떨어진 경우

	if (cnt == 11) return -1;

	bool fall1 = !coin1.isInBoundary();
	bool fall2 = !coin2.isInBoundary();

	if (fall1 && fall2) return -1;
	if (fall1 || fall2) return cnt;

	int ans = -1;

	for (int i = 0; i < 4; i++)
	{
		Point newCoin1;
		newCoin1.r = coin1.r + dR[i];
		newCoin1.c = coin1.c + dC[i];

		Point newCoin2;
		newCoin2.r = coin2.r + dR[i];
		newCoin2.c = coin2.c + dC[i];

		if (newCoin1.isInBoundary() && map[newCoin1.r][newCoin1.c] == '#')
		{
			newCoin1.r = coin1.r;
			newCoin1.c = coin1.c;
		}

		if (newCoin2.isInBoundary() && map[newCoin2.r][newCoin2.c] == '#')
		{
			newCoin2.r = coin2.r;
			newCoin2.c = coin2.c;
		}

		if (visited1[newCoin1.r][newCoin1.c] && visited2[newCoin2.r][newCoin2.c]) continue;

		visited1[newCoin1.r][newCoin1.c] = true;
		visited2[newCoin2.r][newCoin2.c] = true;

		int temp = go(cnt + 1, newCoin1, newCoin2);

		visited1[newCoin1.r][newCoin1.c] = false;
		visited2[newCoin2.r][newCoin2.c] = false;

		if (temp == -1) continue;
		if (ans == -1 || ans > temp) ans = temp;
	}

	return ans;
}


int main(void)
{
	int coinIndex = 0;
	Point coin[2];

	scanf("%d %d", &R, &C);

	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			while (true)
			{
				scanf("%c", &map[i][j]);

				if (map[i][j] != '\n') break;
			}

			if (map[i][j] == 'o')
			{
				coin[coinIndex].r = i;
				coin[coinIndex++].c = j;
			}
		}
	}

	printf("%d\n", go(0, coin[0], coin[1]));

	return 0;
}