시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 128 MB 158 54 23 23.469%

문제

꽃밭에 N*N개의 꽃이 N행 N열로 심어져 있다. 이 꽃밭에는 메뚜기가 한 마리 있는데, 메뚜기는 모든 꽃의 꽃잎의 개수를 알고 있다.

메뚜기는 맨 처음에 R행 C열에 있는 꽃 위에 있고, 다음과 같은 규칙을 지키면서 최대한 많은 꽃을 방문하려고 한다.

1. 메뚜기는 인접한 행 또는 열에 있는 꽃으로 점프할 수 있다. 만약, 인접한 행에 있는 꽃으로 이동할 때는, 적어도 두 열 이상 점프를 해야 한다. 또, 인접한 열에 있는 꽃으로 이동할 때는, 적어도 두 행 이상 점프를 해야 한다.

즉, (r1, c1)에서 (r2, c2)로 점프를 할 수 있으려면 다음과 같은 조건을 만족해야 한다.

- |r1-r2| = 1인 경우 |c1-c2| > 1 또는

- |c1-c2| = 1인 경우 |r1-r2| > 1

2. 점프하려고 하는 칸에 있는 꽃의 꽃잎의 개수는 현재 있는 칸의 꽃잎의 개수보다 많아야 한다.

메뚜기가 최대 몇 개의 꽃을 방문할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1500)

둘째 줄에 메뚜기가 가장 처음에 있는 위치 R과 C가 주어진다. (1 ≤ R, C ≤ N)

다음 N개 줄에는 꽃잎의 수가 주어진다. 꽃잎의 수는 1,000,000보다 작거나 같다.

출력

첫째 줄에 최대 몇 개의 꽃을 방문할 수 있는지 출력한다.

예제 입력 1

4
1 1
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7

예제 출력 1

4
W3sicHJvYmxlbV9pZCI6IjI5NjkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJhNTRcdWI2OWNcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWY0M1x1YmMyZFx1YzVkMCBOKk5cdWFjMWNcdWM3NTggXHVhZjQzXHVjNzc0IE5cdWQ1ODkgTlx1YzVmNFx1Yjg1YyBcdWMyZWNcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVhZjQzXHViYzJkXHVjNWQwXHViMjk0IFx1YmE1NFx1YjY5Y1x1YWUzMFx1YWMwMCBcdWQ1NWMgXHViOWM4XHViOWFjIFx1Yzc4OFx1YjI5NFx1YjM3MCwgXHViYTU0XHViNjljXHVhZTMwXHViMjk0IFx1YmFhOFx1YjRlMCBcdWFmNDNcdWM3NTggXHVhZjQzXHVjNzhlXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWM1NGNcdWFjZTAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhNTRcdWI2OWNcdWFlMzBcdWIyOTQgXHViOWU4IFx1Y2M5OFx1Yzc0Y1x1YzVkMCBSXHVkNTg5IENcdWM1ZjRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWY0MyBcdWM3MDRcdWM1ZDAgXHVjNzg4XHVhY2UwLCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YWRkY1x1Y2U1OVx1Yzc0NCBcdWM5YzBcdWQwYTRcdWJhNzRcdWMxMWMgXHVjZDVjXHViMzAwXHVkNTVjIFx1YjljZVx1Yzc0MCBcdWFmNDNcdWM3NDQgXHViYzI5XHViYjM4XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+MS4gXHViYTU0XHViNjljXHVhZTMwXHViMjk0IFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWQ1ODkgXHViNjEwXHViMjk0IFx1YzVmNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVhZjQzXHVjNzNjXHViODVjIFx1YzgxMFx1ZDUwNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWQ1ODlcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWY0M1x1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHViNTRjXHViMjk0LCBcdWM4MDFcdWM1YjRcdWIzYzQgXHViNDUwIFx1YzVmNCBcdWM3NzRcdWMwYzEgXHVjODEwXHVkNTA0XHViOTdjIFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjYxMCwgXHVjNzc4XHVjODExXHVkNTVjIFx1YzVmNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVhZjQzXHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWI1NGNcdWIyOTQsIFx1YzgwMVx1YzViNFx1YjNjNCBcdWI0NTAgXHVkNTg5IFx1Yzc3NFx1YzBjMSBcdWM4MTBcdWQ1MDRcdWI5N2MgXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOTg5LCAocjEsIGMxKVx1YzVkMFx1YzExYyAocjIsIGMyKVx1Yjg1YyBcdWM4MTBcdWQ1MDRcdWI5N2MgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM3M2NcdWI4MjRcdWJhNzQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+LSB8cjEtcjJ8ID0gMVx1Yzc3OCBcdWFjYmRcdWM2YjAgfGMxLWMyfCAmZ3Q7IDEgXHViNjEwXHViMjk0PFwvcD5cclxuXHJcbjxwPi0gfGMxLWMyfCA9IDFcdWM3NzggXHVhY2JkXHVjNmIwIHxyMS1yMnwgJmd0OyAxPFwvcD5cclxuXHJcbjxwPjIuIFx1YzgxMFx1ZDUwNFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NThcdWIyOTQgXHVjZTc4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWFmNDNcdWM3NTggXHVhZjQzXHVjNzhlXHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCBcdWQ2MDRcdWM3YWMgXHVjNzg4XHViMjk0IFx1Y2U3OFx1Yzc1OCBcdWFmNDNcdWM3OGVcdWM3NTggXHVhYzFjXHVjMjE4XHViY2Y0XHViMmU0IFx1YjljZVx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmE1NFx1YjY5Y1x1YWUzMFx1YWMwMCBcdWNkNWNcdWIzMDAgXHViYTg3IFx1YWMxY1x1Yzc1OCBcdWFmNDNcdWM3NDQgXHViYzI5XHViYjM4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxNTAwKTxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmE1NFx1YjY5Y1x1YWUzMFx1YWMwMCBcdWFjMDBcdWM3YTUgXHVjYzk4XHVjNzRjXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM3MDRcdWNlNTggUlx1YWNmYyBDXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBSLCBDICZsZTsgTik8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWY0M1x1Yzc4ZVx1Yzc1OCBcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFmNDNcdWM3OGVcdWM3NTggXHVjMjE4XHViMjk0IDEsMDAwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjZDVjXHViMzAwIFx1YmE4NyBcdWFjMWNcdWM3NTggXHVhZjQzXHVjNzQ0IFx1YmMyOVx1YmIzOFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyOTY5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU0tBS0FWQUMiLCJkZXNjcmlwdGlvbiI6IjxwPkEgZ3Jhc3Nob3BwZXIgaXMgaW4gYSBmbG93ZXIgZmllbGQuIFRoZSBmaWVsZCBjb250YWlucyBOJm1pZGRvdDtOIGZsb3dlcnMgYXJyYW5nZWQgaW4gTiByb3dzIGFuZCBOIGNvbHVtbnMuIEZvciBlYWNoIGZsb3dlciBpbiB0aGUgZmllbGQsIHdlIGtub3cgaG93IG1hbnkgcGV0YWxzIGl0IGhhcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGdyYXNzaG9wcGVyIGlzIGluaXRpYWxseSBvbiB0aGUgZmxvd2VyIGluIHJvdyBSIGFuZCBjb2x1bW4gQy4gSXRzIGdvYWwgaXMgdG8gdmlzaXQgYXMgbWFueSBmbG93ZXJzIGFzIHBvc3NpYmxlIHdoaWxlIG9iZXlpbmcgdGhlc2UgcnVsZXM6Jm5ic3A7PFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+SXQgY2FuIG9ubHkganVtcCBpbnRvIGFuIGFkamFjZW50IHJvdyBvciBjb2x1bW4uIElmIGl0IGp1bXBzIGludG8gdGhlIGFkamFjZW50IHJvdywgaXQgbXVzdCBqdW1wIGF0IGxlYXN0IHR3byBjb2x1bW5zLCBhbmQgaWYgaXQganVtcHMgaW50byB0aGUgYWRqYWNlbnQgY29sdW1uLCBpdCBtdXN0IGp1bXAgYXQgbGVhc3QgdHdvIHJvd3MuIEluIG90aGVyIHdvcmRzLCBpdCBjYW4ganVtcCBmcm9tIGZsb3dlciAocjxzdWI+MTxcL3N1Yj4sIGM8c3ViPjE8XC9zdWI+KSB0byBmbG93ZXIgKHI8c3ViPjI8XC9zdWI+LCBjPHN1Yj4yPFwvc3ViPikgaWY6Jm5ic3A7XHJcblxyXG5cdDx1bD5cclxuXHRcdDxsaT58cjxzdWI+MTxcL3N1Yj4tcjxzdWI+MjxcL3N1Yj58ID0gMSBhbmQgfGM8c3ViPjE8XC9zdWI+LWM8c3ViPjI8XC9zdWI+fCZndDsgMSBvciZuYnNwOzxcL2xpPlxyXG5cdFx0PGxpPnxjPHN1Yj4xPFwvc3ViPi1jPHN1Yj4yPFwvc3ViPnwgPSAxIGFuZCB8cjxzdWI+MTxcL3N1Yj4tcjxzdWI+MjxcL3N1Yj58Jmd0OyAxJm5ic3A7PFwvbGk+XHJcblx0PFwvdWw+XHJcblx0PFwvbGk+XHJcblx0PGxpPlRoZSBudW1iZXIgb2YgcGV0YWxzIG9uIHRoZSBuZXh0IGZsb3dlciBtdXN0IGJlIHN0cmljdGx5IGxhcmdlciB0aGFuIHRoZSBudW1iZXIgb2YgcGV0YWxzIG9uIHRoZSBwcmV2aW91cyBmbG93ZXIuJm5ic3A7PFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgY2FsY3VsYXRlcyB0aGUgbGFyZ2VzdCBudW1iZXIgb2YgZmxvd2VycyB0aGUgZ3Jhc3Nob3BwZXIgY2FuIHZpc2l0LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdGhlIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAxNTAwKSwgdGhlIHNpemUgb2YgdGhlIGZpZWxkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgaW50ZWdlcnMgUiAoMSAmbGU7IFIgJmxlOyBOKSBhbmQgQyAoMSAmbGU7IEMgJmxlOyBOKSwgdGhlIGdyYXNzaG9wcGVyJiMzOTtzIGluaXRpYWwgcG9zaXRpb24uPFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IE4gbGluZXMgY29udGFpbiBOIHBvc2l0aXZlIGludGVnZXJzIHNlcGFyYXRlZCBieSBzcGFjZXMsIGVhY2ggbGVzcyB0aGFuIDEgMDAwIDAwMCwgdGhlIG51bWJlcnMgb2YgcGV0YWxzIG9uIHRoZSBmbG93ZXJzLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBhIHNpbmdsZSBpbnRlZ2VyICZuZGFzaDsgdGhlIGxhcmdlc3QgbnVtYmVyIG9mIGZsb3dlcnMgdGhlIGdyYXNzaG9wcGVyIGNhbiB2aXNpdC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2008/2009 > Contest #1 5번

  • 문제를 번역한 사람: baekjoon
  • 잘못된 조건을 찾은 사람: rhs0266