End-to-End
НОИ 2020, Контрола 1
Time Limit: 2s, Memory Limit: 64MiB
Ели има матрица от цифри с N реда и M колони. Във всяка клетка има точно една цифра между 0 и 9, включително.
Момичето може да променя матрицата, като сменя цифрите в различни клетки (потенциално нито една или пък всичките). Смяната на цифра X с цифра Y ѝ отнема |X-Y| секунди (тоест, абсолютната разлика между цифрите).
Ели казва, че е "свързала двата края" на матрицата (горния с долния или левия с десния) ако между тях има път от съседни (имащи обща стена) клетки съдържащи една и съща цифра. Момичето иска да свърже както горния с долния, така и левия с десния край на матрицата. Забележете, че за да постигне това, тя трябва да ползва една и съща цифра, тъй като пътищата се пресичат.
Нека разгледаме следния пример:
По дадена началната матрица на Ели, можете ли да определите минималното време, за което тя може да свърже краищата ѝ?
Момичето може да променя матрицата, като сменя цифрите в различни клетки (потенциално нито една или пък всичките). Смяната на цифра X с цифра Y ѝ отнема |X-Y| секунди (тоест, абсолютната разлика между цифрите).
Ели казва, че е "свързала двата края" на матрицата (горния с долния или левия с десния) ако между тях има път от съседни (имащи обща стена) клетки съдържащи една и съща цифра. Момичето иска да свърже както горния с долния, така и левия с десния край на матрицата. Забележете, че за да постигне това, тя трябва да ползва една и съща цифра, тъй като пътищата се пресичат.
Нека разгледаме следния пример:
2753852 9567342 5294979 3180559 |
2753852 8888842 5284888 3180559 |
2753852 9333333 5394979 3380559 |
2753852 7777342 5297777 3180579 |
Началната матрица на момичето има четири реда и седем колони. | Ето един начин, по който можем да постигнем целта за 16 секунди. | Друг начин е следният, постигайки целта за 14 секунди, ползвайки 3-ки. | Трети начин да постигнем целта, отново за 14 секунди, този път със 7-ци. |
По дадена началната матрица на Ели, можете ли да определите минималното време, за което тя може да свърже краищата ѝ?
Вход
На първия ред на стандартния вход ще бъдат зададени целите числа N и M. На всеки от следващите N реда ще има по един стринг съставен от M цифри.
Изход
На единствен ред на стандартния изход изведете едно цяло число – минималния брой секунди, достатъчен да се промени матрицата по желания начин.
Ограничения
- 1 ≤ N, M ≤ 500
Примерен Вход | Примерен Изход |
---|---|
4 7 2753852 9567342 5294979 3180559 | 14 |