Ttururu Tturu
Time limit0.5sMemory limit512 MB
Count self-avoiding walks of length 10 on an R x C grid whose cell contents read exactly "ttururu tturu" (the 5-letter chorus "뚜루루뚜루" written row-wise twice).
- Level
Hard8 of 10
- Topics
- DFS, Brute force, Implementation, Simulation
- Solved
- No attempts yet
Problem
A song called Baby Seokhwan has become popular lately. Its video, which stars a cute baby Seokhwan character, and its catchy ttururu tturu chorus have won over students and office workers across the country.
gs12117, an office worker in Gangnam, fell for the song as well. Hooked on the chorus in particular, gs12117 started writing the ttururu tturu chorus over and over on a sheet of paper divided into R rows and C columns. To write the chorus, gs12117 starts at the leftmost cell of the first row and writes one character per cell going right: 뚜, 루, 루, 뚜, 루, in that order. On reaching the rightmost cell of a row, gs12117 moves to the leftmost cell of the next row.
\nExample on a 7×7 sheet
gs12117 wants to find as many ttururu tturu paths as possible on this sheet. A ttururu tturu path is a path that starts at any cell, moves up, down, left, or right without visiting a cell it has already visited, and reads the characters written in the cells in order, producing exactly ttururu tturu.
Given the size of the sheet, find the number of ttururu tturu paths gs12117 can find. Two paths are different if at the same position in the order they visit different cells.
Input
The first line gives the integers R and C, the number of rows and columns of the sheet (1 ≤ R, C ≤ 12,117).
Output
On the first line, print the number of ttururu tturu paths gs12117 can find.
Hint
In the first sample, the following paths are possible.
