在某個國家，為了讓所有城市排列整齊，政府將所有城市以$m$行$n$列的矩陣方式排列，且為了省錢只建造了左-右、上-下、左上-右下，三種方向的道路。
現在有一個商人從第$0$行第$0$列的城市出發，在不同城市及道路上進行交易，且每次皆只會走向右、下、右下三個方向的道路。
已知：
在第$i$行$j$列的城市可以賺取$p_{i,j}$的錢
在第$i$行$j$列城市通往右方城市的道路上可以賺取$a_{i,j}$的錢
在第$i$行$j$列城市通往下方城市的道路上可以賺取$b_{i,j}$的錢
在第$i$行$j$列城市通往右下方城市的道路上可以賺取$c_{i,j}$的錢
且某些道路因為法令關係而無法通過，請問此商人在抵達第$m$行$n$列的城市前最多可以賺取多少錢
第一行有兩個正整數，分別代表$m$, $n$
接下來有$m*n$行，每行有四個正整數，分別代表第$i$行第$j$列的$p_{i,j}$、$a_{i,j}$、$b_{i,j}$、$c_{i,j}$（$0 <= i < m$，$0 <= j < n$，以$(0, 0), (0, 1), (0, 2), ..., (m-1. n-1)$的順序排列），若該道路無法通過則輸入-1。
輸出商人最多可以賺取多少錢
2 3 1 7 3 -1 5 10 8 2 4 -1 -1 -1 4 5 -1 -1 3 4 -1 -1 2 -1 -1 -1
30
BFS？還是其實有其他方法
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||