2024 : Skakavac
Problem type : Batch
Time limit : 4.0 second(s)
Memory limit : 35 megabyte(s)
Problem type : Batch
Time limit : 4.0 second(s)
Memory limit : 35 megabyte(s)
A grasshopper is in a flower field. The field contains N·N flowers arranged in N rows and N columns. For each flower in the field, we know how many petals it has.
The grasshopper is initially on the flower in row R and column C. Its goal is to visit as many flowers as possible while obeying these rules:
Input
The first line contains the integer N (1 ≤ N ≤ 1500), the size of the field.
The second line contains integers R (1 ≤ R ≤ N) and C (1 ≤ C ≤ N), the grasshopper's initial position.
The next N lines contain N positive integers separated by spaces, each less than 1 000 000, the numbers of petals on the flowers.
Output
Output a single integer – the largest number of flowers the grasshopper can visit.
Scoring
In test data worth 50% of points, N will be at most 100.
In test data worth 80% of points, N will be at most 1000.
Reference: COCI 2008/2009, Contest #1 – October 18, 2008
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
The grasshopper is initially on the flower in row R and column C. Its goal is to visit as many flowers as possible while obeying these rules:
1. It can only jump into an adjacent row or column. If it jumps into the adjacent row, it must jump at least two columns, and if it jumps into the adjacent column, it must jump at least two rows.
In other words, it can jump from flower (r1, c1) to flower (r2, c2) if:
· |r1−r2| = 1 and |c1−c2|> 1; or
· |c1−c2| = 1 and |r1−r2|> 1.
2. The number of petals on the next flower must be strictly larger than the number of petals on the previous flower.
In other words, it can jump from flower (r1, c1) to flower (r2, c2) if:
· |r1−r2| = 1 and |c1−c2|> 1; or
· |c1−c2| = 1 and |r1−r2|> 1.
2. The number of petals on the next flower must be strictly larger than the number of petals on the previous flower.
Task
Write a program that calculates the largest number of flowers the grasshopper can visit.Input
The first line contains the integer N (1 ≤ N ≤ 1500), the size of the field.
The second line contains integers R (1 ≤ R ≤ N) and C (1 ≤ C ≤ N), the grasshopper's initial position.
The next N lines contain N positive integers separated by spaces, each less than 1 000 000, the numbers of petals on the flowers.
Output
Output a single integer – the largest number of flowers the grasshopper can visit.
Scoring
In test data worth 50% of points, N will be at most 100.
In test data worth 80% of points, N will be at most 1000.
Reference: COCI 2008/2009, Contest #1 – October 18, 2008
| ตัวอย่างข้อมูลนำเข้า | ตัวอย่างข้อมูลส่งออก |
| 4 1 1 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 | 4 |
| 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 | 21 |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
กำลังออนไลน์: 21 ผู้เยี่ยมชมและ 0 สมาชิก (0 บอท)