백준 5913번 준규와 사과

문제 링크입니다: https://www.acmicpc.net/problem/5913

준규와 해빈이 둘 다 고려해야한다고 생각들 수 있는 문제이지만 사실 준규가 해빈이의 시작점까지 갈 수 있는 방법의 수를 구하는 문제였습니다.

즉, (0, 0)에서 (4, 4)까지 가는 방법의 수가 정답이였습니다!

#include <iostream>

#include <cstring> //memset

using namespace std;

 

int K;

int result = 0, noBarrier;

int farm[5][5];

 

typedef struct

{

        int y, x;

}Direction;

 

Direction dir[4] = { { 1, 0 },{ -1, 0 },{ 0, 1 },{ 0, -1 } }; //N S E W

 

void howManyWays(int y, int x, int visited)

{

        if (x == 4 && y == 4)

        {

               if (visited == noBarrier)

                       result++;

               return;

        }

 

        for (int i = 0; i < 4; i++)

        {

               int nextY = y + dir[i].y;

               int nextX = x + dir[i].x;

 

               if (nextY >= 0 && nextY < 5 && nextX >= 0 && nextX < 5 && farm[nextY][nextX] != 1)

               {

                       farm[nextY][nextX] = 1;

                       howManyWays(nextY, nextX, visited + 1);

                       farm[nextY][nextX] = 0;

               }

        }

}

 

int main(void)

{

        cin >> K;

        noBarrier = 25 - K; //돌이 없는 칸 수

        memset(farm, 0, sizeof(farm));

        farm[0][0] = 1;

        for (int i = 0; i < K; i++)

        {

               int y, x;

               cin >> y >> x;

               farm[y - 1][x - 1] = 1;

        }

        howManyWays(0, 0, 1);

        cout << result << endl;

        return 0;

}

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~