프로그램 명: koi_block(special judge)
제한시간: 1 초

연아와 연재는 아래 그림과 같은 모양으로 보도블록이 깔린 지역에서 자주 놀곤 한다.

M 개의 행과 N 개의 열로 이루어진 M*N 크기의 보도블록은 2*M*N 개의 타일들로 구성되는데, 이 타일들은 짧은 변과 긴 변의 길이 비가 1:2 인 직사각형 모양으로 크기가 동일하고, 색은 흰색과 회색 두 종류가 있다.

M*N 크기의 보도블록에서 각 행은 위에서 아래로 1부터 M 까지 번호가 매겨져 있고, 각 열은 왼쪽에서 오른쪽으로 1부터 N 까지 번호가 매겨져 있다고 하자. i 행 j 열에는 색이 다른 두 타일이 정사각형 모양으로 맞붙어 배치되어 있는데, 배치된 모양은 i+j 의 값에 따라 다음 두 가지 중 하나이다.

i 행 j 열의 흰색 타일은 (i,j,0) 으로 나타내고 회색 타일은 (i,j,1) 로 나타낸다.

연아와 연재는 이 보도블록에서 자주 게임을 하는데, 이 게임의 규칙은 간단하다.

먼저 보도블록의 크기를 정한다. 그런 다음 이 보도블록에 속한 타일 하나에서 출발하여 아래의 조건을 만족하면서 가능한 많은 개수의 타일을 밟고 지나서 다시 출발한 타일로 되돌아오는 게임이다.

  1. 출발하는 타일은 임의로 정할 수 있다.

  2. 하나의 타일은 정확히 한번만 밟고 지날 수 있다. 단, 출발한 타일은 출발할 때와 도착할 때 한 번씩 두 번 밟게 된다.

  3. 한 타일에서 다음 타일로 이동할 때 반드시 변을 맞대고 있는 타일로 이동해야 한다. 따라서 한 타일에서 이동 가능한 타일은 최대 5개이다. 예를 들면, 그림 1(a)의 1행 2열에 있는 흰색 타일에서는 바로 오른쪽 회색 타일, 바로 아래 흰색 타일, 바로 왼쪽의 흰색 또는 회색 타일로만 이동 가능하다.

예를 들어 그림 1(a)와 같이 2*3 크기의 보도블록에서는 다음과 같은 방법으로 12개의 타일을 모두 지날 수 있다.

(1,1,1) -> (1,1,0) -> (1,2,0) -> (1,2,1) -> (1,3,0) -> (1,3,1) -> (2,3,1) -> (2,3,0) -> (2,2,0) -> (2,2,1) -> (2,1,1) -> (2,1,0) -> (1,1,1)

보도블록의 크기 M*N 이 주어질 때 최대 몇 개의 타일을 지날 수 있는지, 그리고 어떤 순서로 타일을 지나야 최대 개수의 타일을 지나게 되는지를 알아내는 프로그램을 작성 하시오.

프로그램의 실행시간은 1초를 넘을 수 없다. 부분 점수는 없다.

입력

첫 째 줄에 보도블록의 행의 개수 M 과 열의 개수 N 을 나타내는 두 개의 정수가 빈칸을 사이에 두고 주어진다(2≤ M,N ≤100).

출력

입출력 예

입력

2 3

출력

12
1 1 1
1 1 0
1 2 0
1 2 1
1 3 0
1 3 1
2 3 1
2 3 0
2 2 0
2 2 1
2 1 1
2 1 0
출처:koi 2011 중등 지역 4
special judge:Fate
대회 풀이
[질/답] [제출 현황] [푼 후(3)]
[ 채 점 ] [홈으로]  [뒤 로]