2969번 - 메뚜기 다국어

시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 128 MB303794322.396%

문제

꽃밭에 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

예제 입력 2 

5
3 3
20 16 25 17 12
11 13 13 30 17
15 29 10 26 11
27 19 14 24 22
23 21 28 18 13

예제 출력 2 

21
W3sicHJvYmxlbV9pZCI6IjI5NjkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJhNTRcdWI2OWNcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWY0M1x1YmMyZFx1YzVkMCBOKk5cdWFjMWNcdWM3NTggXHVhZjQzXHVjNzc0IE5cdWQ1ODkgTlx1YzVmNFx1Yjg1YyBcdWMyZWNcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVhZjQzXHViYzJkXHVjNWQwXHViMjk0IFx1YmE1NFx1YjY5Y1x1YWUzMFx1YWMwMCBcdWQ1NWMgXHViOWM4XHViOWFjIFx1Yzc4OFx1YjI5NFx1YjM3MCwgXHViYTU0XHViNjljXHVhZTMwXHViMjk0IFx1YmFhOFx1YjRlMCBcdWFmNDNcdWM3NTggXHVhZjQzXHVjNzhlXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWM1NGNcdWFjZTAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhNTRcdWI2OWNcdWFlMzBcdWIyOTQgXHViOWU4IFx1Y2M5OFx1Yzc0Y1x1YzVkMCBSXHVkNTg5IENcdWM1ZjRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWY0MyBcdWM3MDRcdWM1ZDAgXHVjNzg4XHVhY2UwLCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YWRkY1x1Y2U1OVx1Yzc0NCBcdWM5YzBcdWQwYTRcdWJhNzRcdWMxMWMgXHVjZDVjXHViMzAwXHVkNTVjIFx1YjljZVx1Yzc0MCBcdWFmNDNcdWM3NDQgXHViYzI5XHViYjM4XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5cdWJhNTRcdWI2OWNcdWFlMzBcdWIyOTQgXHVjNzc4XHVjODExXHVkNTVjIFx1ZDU4OSBcdWI2MTBcdWIyOTQgXHVjNWY0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWFmNDNcdWM3M2NcdWI4NWMgXHVjODEwXHVkNTA0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHVjNzc4XHVjODExXHVkNTVjIFx1ZDU4OVx1YzVkMCBcdWM3ODhcdWIyOTQgXHVhZjQzXHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWI1NGNcdWIyOTQsIFx1YzgwMVx1YzViNFx1YjNjNCBcdWI0NTAgXHVjNWY0IFx1Yzc3NFx1YzBjMSBcdWM4MTBcdWQ1MDRcdWI5N2MgXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViNjEwLCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHVjNWY0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWFmNDNcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YjU0Y1x1YjI5NCwgXHVjODAxXHVjNWI0XHViM2M0IFx1YjQ1MCBcdWQ1ODkgXHVjNzc0XHVjMGMxIFx1YzgxMFx1ZDUwNFx1Yjk3YyBcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM5ODksIChyPHN1Yj4xPFwvc3ViPiwgYzxzdWI+MTxcL3N1Yj4pXHVjNWQwXHVjMTFjIChyPHN1Yj4yPFwvc3ViPiwgYzxzdWI+MjxcL3N1Yj4pXHViODVjIFx1YzgxMFx1ZDUwNFx1Yjk3YyBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YjgyNFx1YmE3NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LlxyXG5cclxuXHQ8dWw+XHJcblx0XHQ8bGk+fHI8c3ViPjE8XC9zdWI+LXI8c3ViPjI8XC9zdWI+fCA9IDFcdWM3NzggXHVhY2JkXHVjNmIwIHxjPHN1Yj4xPFwvc3ViPi1jPHN1Yj4yPFwvc3ViPnwgJmd0OyAxIFx1YjYxMFx1YjI5NDxcL2xpPlxyXG5cdFx0PGxpPnxjPHN1Yj4xPFwvc3ViPi1jPHN1Yj4yPFwvc3ViPnwgPSAxXHVjNzc4IFx1YWNiZFx1YzZiMCB8cjxzdWI+MTxcL3N1Yj4tcjxzdWI+MjxcL3N1Yj58ICZndDsgMTxcL2xpPlxyXG5cdDxcL3VsPlxyXG5cdDxcL2xpPlxyXG5cdDxsaT5cdWM4MTBcdWQ1MDRcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTU4XHViMjk0IFx1Y2U3OFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVhZjQzXHVjNzU4IFx1YWY0M1x1Yzc4ZVx1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgXHVkNjA0XHVjN2FjIFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWM3NTggXHVhZjQzXHVjNzhlXHVjNzU4IFx1YWMxY1x1YzIxOFx1YmNmNFx1YjJlNCBcdWI5Y2VcdWM1NDRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlx1YmE1NFx1YjY5Y1x1YWUzMFx1YWMwMCBcdWNkNWNcdWIzMDAgXHViYTg3IFx1YWMxY1x1Yzc1OCBcdWFmNDNcdWM3NDQgXHViYzI5XHViYjM4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxNTAwKTxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmE1NFx1YjY5Y1x1YWUzMFx1YWMwMCBcdWFjMDBcdWM3YTUgXHVjYzk4XHVjNzRjXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM3MDRcdWNlNTggUlx1YWNmYyBDXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBSLCBDICZsZTsgTik8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWY0M1x1Yzc4ZVx1Yzc1OCBcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFmNDNcdWM3OGVcdWM3NTggXHVjMjE4XHViMjk0IDEsMDAwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjZDVjXHViMzAwIFx1YmE4NyBcdWFjMWNcdWM3NTggXHVhZjQzXHVjNzQ0IFx1YmMyOVx1YmIzOFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyOTY5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU0tBS0FWQUMiLCJkZXNjcmlwdGlvbiI6IjxwPkEgZ3Jhc3Nob3BwZXIgaXMgaW4gYSBmbG93ZXIgZmllbGQuIFRoZSBmaWVsZCBjb250YWlucyBOJm1pZGRvdDtOIGZsb3dlcnMgYXJyYW5nZWQgaW4gTiByb3dzIGFuZCBOIGNvbHVtbnMuIEZvciBlYWNoIGZsb3dlciBpbiB0aGUgZmllbGQsIHdlIGtub3cgaG93IG1hbnkgcGV0YWxzIGl0IGhhcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGdyYXNzaG9wcGVyIGlzIGluaXRpYWxseSBvbiB0aGUgZmxvd2VyIGluIHJvdyBSIGFuZCBjb2x1bW4gQy4gSXRzIGdvYWwgaXMgdG8gdmlzaXQgYXMgbWFueSBmbG93ZXJzIGFzIHBvc3NpYmxlIHdoaWxlIG9iZXlpbmcgdGhlc2UgcnVsZXM6Jm5ic3A7PFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+SXQgY2FuIG9ubHkganVtcCBpbnRvIGFuIGFkamFjZW50IHJvdyBvciBjb2x1bW4uIElmIGl0IGp1bXBzIGludG8gdGhlIGFkamFjZW50IHJvdywgaXQgbXVzdCBqdW1wIGF0IGxlYXN0IHR3byBjb2x1bW5zLCBhbmQgaWYgaXQganVtcHMgaW50byB0aGUgYWRqYWNlbnQgY29sdW1uLCBpdCBtdXN0IGp1bXAgYXQgbGVhc3QgdHdvIHJvd3MuIEluIG90aGVyIHdvcmRzLCBpdCBjYW4ganVtcCBmcm9tIGZsb3dlciAocjxzdWI+MTxcL3N1Yj4sIGM8c3ViPjE8XC9zdWI+KSB0byBmbG93ZXIgKHI8c3ViPjI8XC9zdWI+LCBjPHN1Yj4yPFwvc3ViPikgaWY6Jm5ic3A7XHJcblxyXG5cdDx1bD5cclxuXHRcdDxsaT58cjxzdWI+MTxcL3N1Yj4tcjxzdWI+MjxcL3N1Yj58ID0gMSBhbmQgfGM8c3ViPjE8XC9zdWI+LWM8c3ViPjI8XC9zdWI+fCZndDsgMSBvciZuYnNwOzxcL2xpPlxyXG5cdFx0PGxpPnxjPHN1Yj4xPFwvc3ViPi1jPHN1Yj4yPFwvc3ViPnwgPSAxIGFuZCB8cjxzdWI+MTxcL3N1Yj4tcjxzdWI+MjxcL3N1Yj58Jmd0OyAxJm5ic3A7PFwvbGk+XHJcblx0PFwvdWw+XHJcblx0PFwvbGk+XHJcblx0PGxpPlRoZSBudW1iZXIgb2YgcGV0YWxzIG9uIHRoZSBuZXh0IGZsb3dlciBtdXN0IGJlIHN0cmljdGx5IGxhcmdlciB0aGFuIHRoZSBudW1iZXIgb2YgcGV0YWxzIG9uIHRoZSBwcmV2aW91cyBmbG93ZXIuJm5ic3A7PFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgY2FsY3VsYXRlcyB0aGUgbGFyZ2VzdCBudW1iZXIgb2YgZmxvd2VycyB0aGUgZ3Jhc3Nob3BwZXIgY2FuIHZpc2l0LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdGhlIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAxNTAwKSwgdGhlIHNpemUgb2YgdGhlIGZpZWxkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgaW50ZWdlcnMgUiAoMSAmbGU7IFIgJmxlOyBOKSBhbmQgQyAoMSAmbGU7IEMgJmxlOyBOKSwgdGhlIGdyYXNzaG9wcGVyJiMzOTtzIGluaXRpYWwgcG9zaXRpb24uPFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IE4gbGluZXMgY29udGFpbiBOIHBvc2l0aXZlIGludGVnZXJzIHNlcGFyYXRlZCBieSBzcGFjZXMsIGVhY2ggbGVzcyB0aGFuIDEgMDAwIDAwMCwgdGhlIG51bWJlcnMgb2YgcGV0YWxzIG9uIHRoZSBmbG93ZXJzLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBhIHNpbmdsZSBpbnRlZ2VyICZuZGFzaDsgdGhlIGxhcmdlc3QgbnVtYmVyIG9mIGZsb3dlcnMgdGhlIGdyYXNzaG9wcGVyIGNhbiB2aXNpdC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

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

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

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말

© 2022 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO

  • 사업자 등록 번호: 541-88-00682
  • 대표자명: 최백준
  • 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
  • 전화번호: 02-521-0487 (이메일로 연락 주세요)
  • 이메일: contacts@startlink.io
  • 통신판매신고번호: 제 2017-서울서초-2193 호