시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB23814513861.883%

문제

유명한 로직 게임 페그는 칩이 다른 칩을 점프해서 점프한 칩을 제거하는 게임이다. 게임은 보드판에 칩이 하나 남을 때 까지 계속한다.

아래 그림은 페그의 초기 상태이다.

  ooo
  ooo
ooooooo
ooo.ooo
ooooooo
  ooo
  ooo

그림에서 'o'는 칩을 나타내며, '.'는 빈 칸을 나타낸다. 플레이어가 칩 하나를 고른다. 그 다음에 고른 칩과 인접한 칸에 칩이 있고 그 다음 칸이 비어있다면, 그 칩을 뛰어넘고 뛰어넘은 칩을 보드판에서 제거한다. (방향은 위, 아래, 오른쪽 왼쪽 중 하나이다) 

보드의 상태가 주어졌을 대, 플레이어가 칩을 움직일 수 있는 올바른 방법의 수를 계산하는 프로그램을 작성하시오.

입력

총 일곱 줄에 걸쳐 보드의 상태가 주어진다. 처음 두 줄과 마지막 두 줄의 첫 번째, 두 번째 문자는 항상 공백이다. 나머지는 'o' 또는 '.'이다.

출력

첫째 줄에 올바른 이동의 수를 출력한다.

예제 입력 1

  ooo  
  ooo  
ooooooo
ooo.ooo
ooooooo
  ooo  
  ooo  

예제 출력 1

4

예제 입력 2

  ooo  
  ooo  
..ooo..
oo...oo
..ooo..
  ooo  
  ooo  

예제 출력 2

12
W3sicHJvYmxlbV9pZCI6IjMwMTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzOThcdWFkZjgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzcyMFx1YmE4NVx1ZDU1YyBcdWI4NWNcdWM5YzEgXHVhYzhjXHVjNzg0IFx1ZDM5OFx1YWRmOFx1YjI5NCBcdWNlNjlcdWM3NzQgXHViMmU0XHViOTc4IFx1Y2U2OVx1Yzc0NCBcdWM4MTBcdWQ1MDRcdWQ1NzRcdWMxMWMgXHVjODEwXHVkNTA0XHVkNTVjIFx1Y2U2OVx1Yzc0NCBcdWM4MWNcdWFjNzBcdWQ1NThcdWIyOTQgXHVhYzhjXHVjNzg0XHVjNzc0XHViMmU0LiBcdWFjOGNcdWM3ODRcdWM3NDAgXHViY2Y0XHViNGRjXHVkMzEwXHVjNWQwIFx1Y2U2OVx1Yzc3NCBcdWQ1NThcdWIwOTggXHViMGE4XHVjNzQ0IFx1YjU0YyBcdWFlNGNcdWM5YzAgXHVhY2M0XHVjMThkXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjNzQwIFx1ZDM5OFx1YWRmOFx1Yzc1OCBcdWNkMDhcdWFlMzAgXHVjMGMxXHVkMGRjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cHJlPlxyXG4gIG9vb1xyXG4gIG9vb1xyXG5vb29vb29vXHJcbm9vby5vb29cclxub29vb29vb1xyXG4gIG9vb1xyXG4gIG9vbzxcL3ByZT5cclxuXHJcbjxwPlx1YWRmOFx1YjliY1x1YzVkMFx1YzExYyAmIzM5O28mIzM5O1x1YjI5NCBcdWNlNjlcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViYTcwLCAmIzM5Oy4mIzM5O1x1YjI5NCBcdWJlNDggXHVjZTc4XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHVhYzAwIFx1Y2U2OSBcdWQ1NThcdWIwOThcdWI5N2MgXHVhY2UwXHViOTc4XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjXHVjNWQwIFx1YWNlMFx1Yjk3OCBcdWNlNjlcdWFjZmMgXHVjNzc4XHVjODExXHVkNTVjIFx1Y2U3OFx1YzVkMCBcdWNlNjlcdWM3NzQgXHVjNzg4XHVhY2UwIFx1YWRmOCBcdWIyZTRcdWM3NGMgXHVjZTc4XHVjNzc0IFx1YmU0NFx1YzViNFx1Yzc4OFx1YjJlNFx1YmE3NCwgXHVhZGY4IFx1Y2U2OVx1Yzc0NCBcdWI2ZjBcdWM1YjRcdWIxMThcdWFjZTAgXHViNmYwXHVjNWI0XHViMTE4XHVjNzQwIFx1Y2U2OVx1Yzc0NCBcdWJjZjRcdWI0ZGNcdWQzMTBcdWM1ZDBcdWMxMWMgXHVjODFjXHVhYzcwXHVkNTVjXHViMmU0LiAoXHViYzI5XHVkNWE1XHVjNzQwIFx1YzcwNCwgXHVjNTQ0XHViNzk4LCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjNjdjXHVjYWJkIFx1YzkxMSBcdWQ1NThcdWIwOThcdWM3NzRcdWIyZTQpJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YmNmNFx1YjRkY1x1Yzc1OCBcdWMwYzFcdWQwZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjMwMCwgXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHVhYzAwIFx1Y2U2OVx1Yzc0NCBcdWM2YzBcdWM5YzFcdWM3N2MgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM2MmNcdWJjMTRcdWI5NzggXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2QxZCBcdWM3N2NcdWFjZjEgXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWJjZjRcdWI0ZGNcdWM3NTggXHVjMGMxXHVkMGRjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjYzk4XHVjNzRjIFx1YjQ1MCBcdWM5MDRcdWFjZmMgXHViOWM4XHVjOWMwXHViOWM5IFx1YjQ1MCBcdWM5MDRcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCwgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWJiMzhcdWM3OTBcdWIyOTQgXHVkNTZkXHVjMGMxIFx1YWNmNVx1YmMzMVx1Yzc3NFx1YjJlNC4gXHViMDk4XHViYTM4XHVjOWMwXHViMjk0ICYjMzk7byYjMzk7IFx1YjYxMFx1YjI5NCAmIzM5Oy4mIzM5O1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWM3NzRcdWIzZDlcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzMDEwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUEVHIiwiZGVzY3JpcHRpb24iOiI8cD5JbiB0aGUgZmFtb3VzIGxvZ2ljIGdhbWUgUGVnLCBwaWVjZXMganVtcCBvdmVyIG90aGVyIHBpZWNlcyB0byByZW1vdmUgdGhlbSBmcm9tIHRoZSBnYW1lLCB1bnRpbCBvbmx5IG9uZSBwaWVjZSBpcyBsZWZ0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5IZXJlIGlzIHRoZSBpbml0aWFsIGxheW91dCBvZiB0aGUgYm9hcmQ6PFwvcD5cclxuXHJcbjxwcmU+XHJcbiAgb29vXHJcbiAgb29vXHJcbm9vb29vb29cclxub29vLm9vb1xyXG5vb29vb29vXHJcbiAgb29vXHJcbiAgb29vPFwvcHJlPlxyXG5cclxuPHA+VGhlIGxvd2VyY2FzZSBsZXR0ZXIgJiMzOTtvJiMzOTsgcmVwcmVzZW50cyBhIHBpZWNlLCB3aGlsZSB0aGUgY2hhcmFjdGVyICYjMzk7LiYjMzk7IGlzIGFuIGVtcHR5IHNxdWFyZS4gSW4gb25lIG1vdmUsIGEgcGxheWVyIG1heSBjaG9vc2Ugb25lIHBpZWNlIGFuZCBvbmUgb2YgdGhlIGZvdXIgbWFpbiBkaXJlY3Rpb25zICh1cCwgZG93biwgbGVmdCwgcmlnaHQpLCBpZiB0aGVyZSBpcyBhbm90aGVyIHBpZWNlIGluIHRoYXQgZGlyZWN0aW9uLCBhbmQgYW4gZW1wdHkgc3F1YXJlIGJlaGluZCBpdC4gVGhlIGNob3NlbiBwaWVjZSBqdW1wcyBvdmVyIHRoZSBvdGhlciBwaWVjZSBhbmQgc2V0dGxlcyBpbiB0aGUgZW1wdHkgc3F1YXJlIGJlaGluZCBpdCwgd2hpbGUgdGhlIHBpZWNlIGJlaW5nIGp1bXBlZCBvdmVyIGlzIHJlbW92ZWQgZnJvbSB0aGUgZ2FtZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgY2FsY3VsYXRlcyB0aGUgbnVtYmVyIG9mIGxlZ2FsIG1vdmVzLCBnaXZlbiB0aGUgc3RhdGUgb2YgdGhlIGJvYXJkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGJvYXJkIGlzIHJlcHJlc2VudGVkIGJ5IHNldmVuIGxpbmVzIGNvbnRhaW5pbmcgc2V2ZW4gY2hhcmFjdGVycyBlYWNoLiBUaGUgZmlyc3QgdHdvIGFuZCBsYXN0IHR3byBjaGFyYWN0ZXJzIG9uIHRoZSBmaXJzdCB0d28gYW5kIGxhc3QgdHdvIGxpbmVzIGFyZSBhbHdheXMgc3BhY2VzLCBhbmQgYWxsIHJlbWFpbmluZyBjaGFyYWN0ZXJzIGFyZSBlaXRoZXIgJiMzOTtvJiMzOTsgKGxvd2VyY2FzZSBsZXR0ZXIpIG9yICYjMzk7LiYjMzk7IChwZXJpb2QgY2hhcmFjdGVyKS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG51bWJlciBvZiBsZWdhbCBtb3Zlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2007/2008 > Contest #1 2번