배관공(plumber) timer 1초 memory - MB

미치광이 배관공 마리오는 2개 도시 사이에 물을 공급하기 위한 네트워크를 건설하려고 한다. 도시의 지도는 R 행 S열의 격자형태로 표현된다. 지도상의 특정 칸은 파이프를 놓기 적합한 곳이 있다.

마리오는 맨왼쪽위의 위쪽 방향에서 부터 맨 오른쪽아래의 아래방향까지를 연결하여 물을 공급하려고한다. 파이프를 놓을 수 있는 칸에는 이를 그대로 두거나 다음과 같이 6개의 형태의 파이프를 놓을 수 있으며, 이를 회전하거나 뒤집어서 놓을 수는 없다. 굵게 표시된 선과 색칠된 부분이 파이프이며, 이 사이로 물이 흐르게 된다.

물이 흐르는 시작점과 끝점 사이에 물이 흐를 수 있게 파이프를 배치하는 경우의 수를 구하는 프로그램을 작성하라. 단, 놓여진 파이프 안에는 모두 물이 흘러야 한다. 상하좌우로 인접한 파이프 끼리는 맞닿아서 물이 흐를 수 있게 연결되어야 한다.

맨 위의 왼쪽 칸에는 3, 4번째 파이프를 사용할 수 있으며, 맨 아래쪽 오른쪽칸의 경우에는 4, 5번째 파이프를 사용할 수 있다.