#include <iostream> using namespace std; int maze[102][102];//迷宮矩陣 int main() {int n;cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)cin>>maze[i][j];//輸入值 }int x=1,y=1,money=maze[1][1];//商人的初始位置while(x<n&&y<n)//防止商人出界{if(maze[x+1][y]<=maze[x][y+1]) {money=maze[x+1][y]+money;x++;}else{money=maze[x][y+1]+money;y++;}} if(x>=n){for(;y<=n;)money=maze[x][++y]+money;}else{for(;x<=n;)money=maze[++x][y]+money;}cout<<money; }

上面為代碼。

題目：一個商人穿過一個N×N的正方形的網格，去參加一個非常重要的商務活動。他要從網格的左上角進，右下角出。每穿越中間1個小方格，都要花費1個單位時間。商人必須在(2N-1)個單位時間穿越出去。而在經過中間的每個小方格時，都需要繳納一定的費用。

這個商人期望在規定時間內用最少費用穿越出去。請問至少需要多少費用？

注意：不能對角穿越各個小方格（即，只能向上下左右四個方向移動且不能離開網格）

輸入格式:

第一行是一個整數，表示正方形的寬度N (1≤N<100)；

后面N行，每行N個不大于100的整數，為網格上每個小方格的費用。

輸出格式:

至少需要的費用。

輸入樣例:

5 1 4 6 8 10 2 5 7 15 17 6 8 9 18 20 10 11 12 19 21 20 23 25 29 33

輸出樣例:

109

樣例中，最小值為109=1+2+5+7+9+12+19+21+33。

思路：

1.從總體來看，本題中商人要從左上角進入，右下角出。這意味著我們可以將商人的初始位置定為（1，1）。為了避免打代碼時腦子混亂，我們可以直接從數組下標為【1】單元開始賦值，這樣子打代碼時就不用減一了。（前提是數組要設大一點，比如如果n最大為200，那就要把數組長設置為201或以上）

2.從細節上看，本題商人必須在（2N-1）個單位時間內穿越出去。（2N-1）是什么概念呢？就是商人圍著矩陣最外層走半圈的耗時。這意味著時間是非常緊的----商人不能往回走（就是往上或者往左走）這點很重要！！！（朋友們可以自己畫個圖走一下來感覺）

3.整合以下，就是商人從（1，1）開始走，通過比較下面和右邊格子數字的大小來進行移動（不用管左邊和上面的格子，因為沒有時間）如果走到了最下面，那就往右邊走就行了，不用管其大小（還是那個道理，不用管左邊和上面！！）直到走至（n,n)--也就是右下角的位置。走到最右邊時同理，只用管下面就行了。

思路理清楚后代碼就不難了，相信各位朋友一定也有自己的見解，歡迎評論留言！

ps：這是本人 (18歲計算機菜鳥) 第一次寫博客，可能語言描述不是很到位，歡迎各位大佬批評與指正！！

總結

以上是生活随笔為你收集整理的最低通行费 C++（PTA)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。