시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 20436 5748 4256 27.178%

문제

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

힌트

W3sicHJvYmxlbV9pZCI6IjE4OTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MTBcdWQ1MDQiLCJkZXNjcmlwdGlvbiI6IjxwPk4mdGltZXM7TiBcdWFjOGNcdWM3ODRcdWQzMTBcdWM1ZDAgXHVjMjE4XHVhYzAwIFx1YzgwMVx1ZDYwMFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM3NTggXHViYWE5XHVkNDVjXHViMjk0IFx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmQgXHVjNzA0IFx1Y2U3OFx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzU0NFx1Yjc5OCBcdWNlNzhcdWM3M2NcdWI4NWMgXHVhZGRjXHVjZTU5XHVjNWQwIFx1YjlkZVx1YWM4YyBcdWM4MTBcdWQ1MDRcdWI5N2MgXHVkNTc0XHVjMTFjIFx1YWMwMFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWNlNzhcdWM1ZDAgXHVjODAxXHVkNjAwXHVjNzg4XHViMjk0IFx1YzIxOFx1YjI5NCBcdWQ2MDRcdWM3YWMgXHVjZTc4XHVjNWQwXHVjMTFjIFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuIFx1YmMxOFx1YjRkY1x1YzJkYyBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3NzRcdWIwOTggXHVjNTQ0XHViNzk4XHVjYWJkXHVjNzNjXHViODVjXHViOWNjIFx1Yzc3NFx1YjNkOVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIDBcdWM3NDAgXHViMzU0IFx1Yzc3NFx1YzBjMSBcdWM5YzRcdWQ1ODlcdWM3NDQgXHViOWM5XHViMjk0IFx1Yzg4NVx1Y2MyOVx1YzgxMFx1Yzc3NFx1YmE3MCwgXHVkNTZkXHVjMGMxIFx1ZDYwNFx1YzdhYyBcdWNlNzhcdWM1ZDAgXHVjODAxXHVkNjAwXHVjNzg4XHViMjk0IFx1YzIxOFx1YjljY1x1ZDA3YyBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3NzRcdWIwOTggXHVjNTQ0XHViNzk4XHViODVjIFx1YWMwMFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1ZDU1YyBcdWJjODggXHVjODEwXHVkNTA0XHViOTdjIFx1ZDU2MCBcdWI1NGMsIFx1YmMyOVx1ZDVhNVx1Yzc0NCBcdWJjMTRcdWFmYjhcdWJhNzQgXHVjNTQ4IFx1YjQxY1x1YjJlNC4gXHVjOTg5LCBcdWQ1NWMgXHVjZTc4XHVjNWQwXHVjMTFjIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzczY1x1Yjg1YyBcdWM4MTBcdWQ1MDRcdWI5N2MgXHVkNTU4XHVhYzcwXHViMDk4LCBcdWM1NDRcdWI3OThcdWI4NWMgXHVjODEwXHVkNTA0XHViOTdjIFx1ZDU1OFx1YjI5NCBcdWI0NTAgXHVhY2JkXHVjNmIwXHViOWNjIFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAwXHVjN2E1IFx1YzY3Y1x1Y2FiZCBcdWM3MDQgXHVjZTc4XHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjNTQ0XHViNzk4IFx1Y2U3OFx1YzczY1x1Yjg1YyBcdWFkZGNcdWNlNTlcdWM1ZDAgXHViOWRlXHVhYzhjIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWM4Y1x1Yzc4NCBcdWQzMTBcdWM3NTggXHVkMDZjXHVhZTMwIE4gKDQgJmxlOyBOICZsZTsgMTAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1Y2U3OFx1YzVkMCBcdWM4MDFcdWQ2MDBcdWM4MzggXHVjNzg4XHViMjk0IFx1YzIxOFx1YWMwMCBOXHVhYzFjXHVjNTI5IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjZTc4XHVjNWQwIFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YjI5NCBcdWMyMThcdWIyOTQgMFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCA5XHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjODE1XHVjMjE4XHVjNzc0XHViYTcwLCBcdWFjMDBcdWM3YTUgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzU0NFx1Yjc5OCBcdWNlNzhcdWM1ZDBcdWIyOTQgXHVkNTZkXHVjMGMxIDBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmQgXHVjNzA0IFx1Y2U3OFx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzU0NFx1Yjc5OCBcdWNlNzhcdWM3M2NcdWI4NWMgXHViYjM4XHVjODFjXHVjNzU4IFx1YWRkY1x1Y2U1OVx1YzVkMCBcdWI5ZGVcdWFjOGMgXHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2JkXHViODVjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuJm5ic3A7PHNwYW4gc3R5bGU9XCJsaW5lLWhlaWdodDoxLjZlbVwiPlx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgMjxcL3NwYW4+PHN1cCBzdHlsZT1cImxpbmUtaGVpZ2h0OjEuNmVtXCI+NjM8XC9zdXA+PHNwYW4gc3R5bGU9XCJsaW5lLWhlaWdodDoxLjZlbVwiPi0xXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuPFwvc3Bhbj48XC9wPlxyXG4iLCJoaW50IjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL0p1ZGdlT25saW5lXC91cGxvYWRcLzIwMTAwN1wvZDEuUE5HXCIgc3R5bGU9XCJoZWlnaHQ6MTQ5cHg7IGxpbmUtaGVpZ2h0OjEuNmVtOyB3aWR0aDo1ODBweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTg5MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ikp1bXAgVGhlIEJvYXJkISIsImRlc2NyaXB0aW9uIjoiPHA+QW4gbiAmdGltZXM7IG4gZ2FtZSBib2FyZCBpcyBwb3B1bGF0ZWQgd2l0aCBpbnRlZ2Vycywgb25lIG5vbm5lZ2F0aXZlIGludGVnZXIgcGVyIHNxdWFyZS4gVGhlIGdvYWwgaXMgdG8ganVtcCBhbG9uZyBhbnkgbGVnaXRpbWF0ZSBwYXRoIGZyb20gdGhlIHVwcGVyIGxlZnQgY29ybmVyIHRvIHRoZSBsb3dlciByaWdodCBjb3JuZXIgb2YgdGhlIGJvYXJkLiBUaGUgaW50ZWdlciBpbiBhbnkgb25lIHNxdWFyZSBkaWN0YXRlcyBob3cgbGFyZ2UgYSBzdGVwIGF3YXkgZnJvbSB0aGF0IGxvY2F0aW9uIG11c3QgYmUuIElmIHRoZSBzdGVwIHNpemUgd291bGQgYWR2YW5jZSB0cmF2ZWwgb2ZmIHRoZSBnYW1lIGJvYXJkLCB0aGVuIGEgc3RlcCBpbiB0aGF0IHBhcnRpY3VsYXIgZGlyZWN0aW9uIGlzIGZvcmJpZGRlbi4gQWxsIHN0ZXBzIG11c3QgYmUgZWl0aGVyIHRvIHRoZSByaWdodCBvciB0b3dhcmQgdGhlIGJvdHRvbS4gTm90ZSB0aGF0IGEgMCBpcyBhIGRlYWQgZW5kIHdoaWNoIHByZXZlbnRzIGFueSBmdXJ0aGVyIHByb2dyZXNzLjxcL3A+XHJcblxyXG48cD5Db25zaWRlciB0aGUgNCAmdGltZXM7IDQgYm9hcmQgc2hvd24gaW4gRmlndXJlIDEsIHdoZXJlIHRoZSBzb2xpZCBjaXJjbGUgaWRlbnRpZmllcyB0aGUgc3RhcnQgcG9zaXRpb24gYW5kIHRoZSBkYXNoZWQgY2lyY2xlIGlkZW50aWZpZXMgdGhlIHRhcmdldC4gRmlndXJlIDIgc2hvd3MgdGhlIHRocmVlIGxlZ2l0aW1hdGUgcGF0aHMgZnJvbSB0aGUgc3RhcnQgdG8gdGhlIHRhcmdldCwgd2l0aCB0aGUgaXJyZWxldmFudCBudW1iZXJzIGluIGVhY2ggcmVtb3ZlZC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9qdW1wKDMpLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE0MHB4OyB3aWR0aDo0OTJweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Zb3VyIHRhc2sgaXMgdG8gd3JpdGUgYSBwcm9ncmFtIHRoYXQgZGV0ZXJtaW5lcyB0aGUgbnVtYmVyIG9mIGxlZ2l0aW1hdGUgcGF0aHMgZnJvbSB0aGUgdXBwZXIgbGVmdCBjb3JuZXIgdG8gdGhlIGxvd2VyIHJpZ2h0IGNvcm5lci48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb250YWlucyBhIGZpcnN0IGxpbmUgd2l0aCBhIHNpbmdsZSBwb3NpdGl2ZSBpbnRlZ2VyIG4sIDQgJmxlOyBuICZsZTsgMTAwLCB3aGljaCBpcyB0aGUgbnVtYmVyIG9mIHJvd3MgaW4gdGhpcyBib2FyZC4gVGhpcyBpcyBmb2xsb3dlZCBieSBuIHJvd3Mgb2YgZGF0YS4gRWFjaCByb3cgY29udGFpbnMgbiBpbnRlZ2VycywgZWFjaCBvbmUgZnJvbSB0aGUgcmFuZ2UgMCZoZWxsaXA7OS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IHNob3VsZCBjb25zaXN0IG9mIGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyBhIHNpbmdsZSBpbnRlZ2VyLCB3aGljaCBpcyB0aGUgbnVtYmVyIG9mIGxlZ2l0aW1hdGUgcGF0aHMgZnJvbSB0aGUgdXBwZXIgbGVmdCBjb3JuZXIgdG8gdGhlIGxvd2VyIHJpZ2h0IGNvcm5lci48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2006 6번