승현이는 자전거를 이용해서 호숫가를 산책하려고 한다. 이 호숫가는 가로 N, 세로 N의 격자 상에서 땅과 호수로 이루어져 있다. 허나, 승현이의 자전거의 기어가 고장났기 때문에 좌회전은 할 수 없고, 우회전은 최대 3번밖에 하지 못한다.
승현이는 산책을 하면서 네 방향(동, 서, 남, 북)으로 모두 산책하고 싶어 한다(그냥 각 방향으로 한 칸 이상 이동하면 된다). 하지만 승현이는 새로운 곳만 방문하길 원하므로 같은 격자를 두 번 이상 갈 수 없다. 승현이는 당연히 호수가 있는 곳으로는 갈 수 없다.
위 그림은 주어진 지도에서 승현이가 공원을 산책할 수 있는 세 가지 방법을 나타낸 것이다. 승현이가 산책을 하면서 방문할 수 있는 최대 격자의 수를 구하여라. 단, 승현이를 만족하는 경로가 1개 이상 존재한다.
전체 데이터의 20%는 N이 50 이하이고, 전체 데이터의 50%는 N이 350 이하이다.
입력 6 9 2 1 2 4 4 4 6 2 6 3 5 3 4 6 5 1 2 6 출력 14
출처 : Balkan Olympiad in Informatics 2012, Day 1 Task 3 http://boi2012.dms.rs/index.php?action=show&data=tasks 번역: functionx