시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 13645 3836 2856 27.107%

문제

N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다.

각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두 경우만 존재한다.

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 오른쪽 아래 칸에는 항상 0이 주어진다.

출력

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 문제의 규칙에 맞게 갈 수 있는 경로의 개수를 출력한다. 경로의 개수는 263-1보다 작거나 같다.

예제 입력 1

4
2 3 3 1
1 2 1 3
1 2 3 1
3 1 1 0

예제 출력 1

3

힌트

W3sicHJvYmxlbV9pZCI6IjE4OTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MTBcdWQ1MDQiLCJkZXNjcmlwdGlvbiI6IjxwPk4mdGltZXM7TiBcdWFjOGNcdWM3ODRcdWQzMTBcdWM1ZDAgXHVjMjE4XHVhYzAwIFx1YzgwMVx1ZDYwMFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM3NTggXHViYWE5XHVkNDVjXHViMjk0IFx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmQgXHVjNzA0IFx1Y2U3OFx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzU0NFx1Yjc5OCBcdWNlNzhcdWM3M2NcdWI4NWMgXHVhZGRjXHVjZTU5XHVjNWQwIFx1YjlkZVx1YWM4YyBcdWM4MTBcdWQ1MDRcdWI5N2MgXHVkNTc0XHVjMTFjIFx1YWMwMFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWNlNzhcdWM1ZDAgXHVjODAxXHVkNjAwXHVjNzg4XHViMjk0IFx1YzIxOFx1YjI5NCBcdWQ2MDRcdWM3YWMgXHVjZTc4XHVjNWQwXHVjMTFjIFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuIFx1YmMxOFx1YjRkY1x1YzJkYyBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3NzRcdWIwOTggXHVjNTQ0XHViNzk4XHVjYWJkXHVjNzNjXHViODVjXHViOWNjIFx1Yzc3NFx1YjNkOVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIDBcdWM3NDAgXHViMzU0IFx1Yzc3NFx1YzBjMSBcdWM5YzRcdWQ1ODlcdWM3NDQgXHViOWM5XHViMjk0IFx1Yzg4NVx1Y2MyOVx1YzgxMFx1Yzc3NFx1YmE3MCwgXHVkNTZkXHVjMGMxIFx1ZDYwNFx1YzdhYyBcdWNlNzhcdWM1ZDAgXHVjODAxXHVkNjAwXHVjNzg4XHViMjk0IFx1YzIxOFx1YjljY1x1ZDA3YyBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3NzRcdWIwOTggXHVjNTQ0XHViNzk4XHViODVjIFx1YWMwMFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1ZDU1YyBcdWJjODggXHVjODEwXHVkNTA0XHViOTdjIFx1ZDU2MCBcdWI1NGMsIFx1YmMyOVx1ZDVhNVx1Yzc0NCBcdWJjMTRcdWFmYjhcdWJhNzQgXHVjNTQ4XHViNDFjXHViMmU0LiBcdWM5ODksIFx1ZDU1YyBcdWNlNzhcdWM1ZDBcdWMxMWMgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzNjXHViODVjIFx1YzgxMFx1ZDUwNFx1Yjk3YyBcdWQ1NThcdWFjNzBcdWIwOTgsIFx1YzU0NFx1Yjc5OFx1Yjg1YyBcdWM4MTBcdWQ1MDRcdWI5N2MgXHVkNTU4XHViMjk0IFx1YjQ1MCBcdWFjYmRcdWM2YjBcdWI5Y2MgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDBcdWM3YTUgXHVjNjdjXHVjYWJkIFx1YzcwNCBcdWNlNzhcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM1NDRcdWI3OTggXHVjZTc4XHVjNzNjXHViODVjIFx1YWRkY1x1Y2U1OVx1YzVkMCBcdWI5ZGVcdWFjOGMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2JkXHViODVjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhYzhjXHVjNzg0IFx1ZDMxMFx1Yzc1OCBcdWQwNmNcdWFlMzAgTiAoNCAmbGU7IE4gJmxlOyAxMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVjZTc4XHVjNWQwIFx1YzgwMVx1ZDYwMFx1YzgzOCBcdWM3ODhcdWIyOTQgXHVjMjE4XHVhYzAwIE5cdWFjMWNcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWNlNzhcdWM1ZDAgXHVjODAxXHVkNjAwXHVjNzg4XHViMjk0IFx1YzIxOFx1YjI5NCAwXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIDlcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM4MTVcdWMyMThcdWM3NzRcdWJhNzAsIFx1YWMwMFx1YzdhNSBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjNTQ0XHViNzk4IFx1Y2U3OFx1YzVkMFx1YjI5NCBcdWQ1NmRcdWMwYzEgMFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAwXHVjN2E1IFx1YzY3Y1x1Y2FiZCBcdWM3MDQgXHVjZTc4XHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjNTQ0XHViNzk4IFx1Y2U3OFx1YzczY1x1Yjg1YyBcdWJiMzhcdWM4MWNcdWM3NTggXHVhZGRjXHVjZTU5XHVjNWQwIFx1YjlkZVx1YWM4YyBcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWI4NWNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4mbmJzcDs8c3BhbiBzdHlsZT1cImxpbmUtaGVpZ2h0OjEuNmVtXCI+XHVhY2JkXHViODVjXHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCAyPFwvc3Bhbj48c3VwIHN0eWxlPVwibGluZS1oZWlnaHQ6MS42ZW1cIj42MzxcL3N1cD48c3BhbiBzdHlsZT1cImxpbmUtaGVpZ2h0OjEuNmVtXCI+LTFcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC48XC9zcGFuPjxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvSnVkZ2VPbmxpbmVcL3VwbG9hZFwvMjAxMDA3XC9kMS5QTkdcIiBzdHlsZT1cImhlaWdodDoxNDlweDsgbGluZS1oZWlnaHQ6MS42ZW07IHdpZHRoOjU4MHB4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxODkwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSnVtcCBUaGUgQm9hcmQhIiwiZGVzY3JpcHRpb24iOiI8cD5BbiBuICZ0aW1lczsgbiBnYW1lIGJvYXJkIGlzIHBvcHVsYXRlZCB3aXRoIGludGVnZXJzLCBvbmUgbm9ubmVnYXRpdmUgaW50ZWdlciBwZXIgc3F1YXJlLiBUaGUgZ29hbCBpcyB0byBqdW1wIGFsb25nIGFueSBsZWdpdGltYXRlIHBhdGggZnJvbSB0aGUgdXBwZXIgbGVmdCBjb3JuZXIgdG8gdGhlIGxvd2VyIHJpZ2h0IGNvcm5lciBvZiB0aGUgYm9hcmQuIFRoZSBpbnRlZ2VyIGluIGFueSBvbmUgc3F1YXJlIGRpY3RhdGVzIGhvdyBsYXJnZSBhIHN0ZXAgYXdheSBmcm9tIHRoYXQgbG9jYXRpb24gbXVzdCBiZS4gSWYgdGhlIHN0ZXAgc2l6ZSB3b3VsZCBhZHZhbmNlIHRyYXZlbCBvZmYgdGhlIGdhbWUgYm9hcmQsIHRoZW4gYSBzdGVwIGluIHRoYXQgcGFydGljdWxhciBkaXJlY3Rpb24gaXMgZm9yYmlkZGVuLiBBbGwgc3RlcHMgbXVzdCBiZSBlaXRoZXIgdG8gdGhlIHJpZ2h0IG9yIHRvd2FyZCB0aGUgYm90dG9tLiBOb3RlIHRoYXQgYSAwIGlzIGEgZGVhZCBlbmQgd2hpY2ggcHJldmVudHMgYW55IGZ1cnRoZXIgcHJvZ3Jlc3MuPFwvcD5cclxuXHJcbjxwPkNvbnNpZGVyIHRoZSA0ICZ0aW1lczsgNCBib2FyZCBzaG93biBpbiBGaWd1cmUgMSwgd2hlcmUgdGhlIHNvbGlkIGNpcmNsZSBpZGVudGlmaWVzIHRoZSBzdGFydCBwb3NpdGlvbiBhbmQgdGhlIGRhc2hlZCBjaXJjbGUgaWRlbnRpZmllcyB0aGUgdGFyZ2V0LiBGaWd1cmUgMiBzaG93cyB0aGUgdGhyZWUgbGVnaXRpbWF0ZSBwYXRocyBmcm9tIHRoZSBzdGFydCB0byB0aGUgdGFyZ2V0LCB3aXRoIHRoZSBpcnJlbGV2YW50IG51bWJlcnMgaW4gZWFjaCByZW1vdmVkLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2p1bXAoMykucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTQwcHg7IHdpZHRoOjQ5MnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0byB3cml0ZSBhIHByb2dyYW0gdGhhdCBkZXRlcm1pbmVzIHRoZSBudW1iZXIgb2YgbGVnaXRpbWF0ZSBwYXRocyBmcm9tIHRoZSB1cHBlciBsZWZ0IGNvcm5lciB0byB0aGUgbG93ZXIgcmlnaHQgY29ybmVyLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnRhaW5zIGEgZmlyc3QgbGluZSB3aXRoIGEgc2luZ2xlIHBvc2l0aXZlIGludGVnZXIgbiwgNCAmbGU7IG4gJmxlOyAxMDAsIHdoaWNoIGlzIHRoZSBudW1iZXIgb2Ygcm93cyBpbiB0aGlzIGJvYXJkLiBUaGlzIGlzIGZvbGxvd2VkIGJ5IG4gcm93cyBvZiBkYXRhLiBFYWNoIHJvdyBjb250YWlucyBuIGludGVnZXJzLCBlYWNoIG9uZSBmcm9tIHRoZSByYW5nZSAwJmhlbGxpcDs5LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvdXRwdXQgc2hvdWxkIGNvbnNpc3Qgb2YgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIGEgc2luZ2xlIGludGVnZXIsIHdoaWNoIGlzIHRoZSBudW1iZXIgb2YgbGVnaXRpbWF0ZSBwYXRocyBmcm9tIHRoZSB1cHBlciBsZWZ0IGNvcm5lciB0byB0aGUgbG93ZXIgcmlnaHQgY29ybmVyLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2006 6번