a123. TOI 2026/06 潛力組：駕駛汽車

題目描述

一座城市以 M 列、N 欄的網格表示，座標由 (0,0) 到 (M−1,N−1)。數值 −1 的格子禁止進入，其餘格子的數值表示每次經過時造成的車輛損傷。車輛可向上、下、左、右移動到相鄰格子，不能超出邊界。

車輛從左上角駛往右下角。第一次選擇行進方向不收取額外損傷；之後每次改變方向，另增加 1 單位損傷。請找出可完成旅程的最小總損傷。

輸入格式

第一行有 M、N。接著 M 行各有 N 個整數，表示網格。

• 2 ≤ M、N ≤ 500
• 每格數值介於 −1 與 9
• 起點與終點的數值皆為 0。

輸出格式

輸出最小總損傷；若終點無法到達，輸出 −1。

來源

TOI 2026 年 6 月潛力組〈駕駛汽車〉。本敘述重新撰寫；範例與測資為另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202606/Driving.pdf