資源簡介
給定一個N*N 的方形網格，設其左上角為起點◎，坐標為（1，1），X 軸向右為正，Y軸向下為正，每個方格邊長為1，如圖所示。一輛汽車從起點◎出發駛向右下角終點▲，其坐標為（N，N）。在若干個網格交叉點處，設置了油庫，可供汽車在行駛途中加油。汽車在行駛過程中應遵守如下規則：
(1)汽車只能沿網格邊行駛，裝滿油后能行駛K 條網格邊。出發時汽車已裝滿油，在起點與終點處不設油庫。
(2)汽車經過一條網格邊時，若其X 坐標或Y 坐標減小，則應付費用B，否則免付費用。
(3)汽車在行駛過程中遇油庫則應加滿油并付加油費用A。
(4)在需要時可在網格點處增設油庫，并付增設油庫費用C（不含加油費用A）。
(5)(1)～(4)中的各數N、K、A、B、C均為正整數，且滿足約束：2 ≤ N ≤100，2 ≤ K ≤10。設計一個算法，求出汽車從起點出發到達終點的一條所付費用最少的行駛路線。
代碼片段和文件信息
#include
#include
void?main（）
{
int?ijkpqxy;
int?NKABC;
int?map[81][81];//記錄各個點的信息
int?cost[81][81][10];
int?min;
int?s[4][3];//4種行走方式
FILE?*fp;
//從輸入文件中讀數據
fp=fopen（“input.txt““rt“）;
fscanf（fp“%d%d%d%d%d“&N&K&A&B&C）;
for（i=1;i<=N;i++）
for（j=1;j<=N;j++）
fscanf（fp“%d“&map[i][j]）;
fclose（fp）;
//初始化行走方式的數組
s[0][0]=-1;
s[0][1]=0;
s[0][2]=0;
s[1][0]=0;
s[1][1]=-1;
s[1][2]=0;
s[2][0]=1;
s[2][1]=0;
s[2][2]=B;
s[3][0]=0;
s[3][1]=1;
s[3][2]=B;
for（i=1;i<=N;i++）
for（j=1;j<=N;j++）
for（k=0;k<=K+1;k++）?//注意這里！！！！
cost[i][j][k]=10000;
//走到11點的費用為0
for（k=0;k<=K;k++）
cost[1][1][k]=0;
y=1;
?
while（y!=0）//修改的行數，當y等于0時說明所有數據為最優數據，跳出循環
{
//printf（“%d\n“y）;
y=0;
for（i=1;i<=N;i++）
{
for（j=1;j<=N;j++）
{
if（i!=1||j!=1）?//ij同時為0時跳到下一次循環
{
for（p=0;p<=K;p++）//剩余的油量
{
min=10000;
for（q=0;q<4;q++）//4種走法
{
if（（i==1&&q==0）||（j==1&&q==1）||（i==N&&q==2）||（j==N&&q==3））//邊界情況
continue;
if（cost[i+s[q][0]][j+s[q][1]][p+1]+s[q][2]
}
if（min<10000）//說明有路可以走過去
{
if（cost[i][j][p]>min+A*map[i][j]）?//花費等于min+A*map[i][j]是合理情況，不合理情況時y++?用來做標記
y++;
cost[i][j][p]=min;
if（map[i][j]==1）
{
cost[i][j][0]+=A;
for（x=1;x<=K;x++）
cost[i][j][x]=cost[i][j][0];
break;
}?
}
else?//沒有路可以過去
{
cost[i][j][p]=cost[i][j][0]+C+A;
for（x=p+1;x<=K;x++）
cost[i][j][x]=cost[i][j][p];
break;
}
}
}
}
}
}
fp=fopen（“output.txt““w“）;
fprintf（fp“%d\n“cost[N][N][0]）;
fclose（fp）;
system（“pause“）;
}?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????文件???????1992??2013-04-08?23:42??汽車加油問題\3-7.c
?????文件???????3365??2013-04-04?21:31??汽車加油問題\3-7.dsp
?????文件????????514??2013-04-05?00:42??汽車加油問題\3-7.dsw
?????文件??????41984??2013-04-08?23:42??汽車加油問題\3-7.ncb
?????文件??????48640??2013-04-08?23:42??汽車加油問題\3-7.opt
?????文件????????731??2013-04-08?23:40??汽車加油問題\3-7.plg
?????文件?????200792??2013-04-08?23:40??汽車加油問題\Debug\3-7.exe
?????文件?????213956??2013-04-08?23:40??汽車加油問題\Debug\3-7.ilk
?????文件???????5200??2013-04-08?23:40??汽車加油問題\Debug\3-7.obj
?????文件?????184616??2013-04-08?23:40??汽車加油問題\Debug\3-7.pch
?????文件?????525312??2013-04-08?23:40??汽車加油問題\Debug\3-7.pdb
?????文件??????33792??2013-04-08?23:40??汽車加油問題\Debug\vc60.idb
?????文件??????53248??2013-04-08?23:40??汽車加油問題\Debug\vc60.pdb
?????文件????????116??2013-04-01?07:42??汽車加油問題\input.txt
?????文件??????????4??2013-04-08?23:40??汽車加油問題\output.txt
?????文件??????56832??2013-04-08?23:38??算法實現題?汽車加油行駛問題.doc
?????目錄??????????0??2013-04-08?23:40??汽車加油問題\Debug
?????目錄??????????0??2013-04-08?23:42??汽車加油問題
-----------?---------??----------?-----??----
??????????????1371094????????????????????18
評論
共有 條評論