//?algorithm.cpp?:?定義控制臺應用程序的入口點。
//

#include?“stdafx.h“
#include
#include
#include
#include
using?namespace?std;

//本函數功能為找出最優路徑并輸出到指定路徑文件中
void?diamond（int?**aint?m?int?n）
{???int?b;

??//初始化一個全為0的數組d，用來存放最優路徑中雜技演員處在每一行的列號：d[i][j]表示當小丑處在第i行第j個樹樁上時，下一步跳上的樹樁的列號（行號為i+1）
	int?**d?=?new?int*[m];??
????for（int?i=0;?i????????d[i]?=?new?int[n];
	for（int?i=0;i		for（int?j=0;j			d[i][j]=0;
	

	for（int?i=1;i	{
???//考慮邊界情況：當處在第0列時，下一步可能跳上的只可能是第0列和第1列，比較第m-i行這兩列的值的大小并把較大者與a[m-i-1][0]上的數值相加存放在a[m-i-1][0]中
		if（a[m-i][0]>=a[m-i][1]）{????????????
			a[m-i-1][0]=a[m-i][0]+a[m-i-1][0];
			d[m-i-1][0]=0;
		}
		else{
		????a[m-i-1][0]=a[m-i][1]+a[m-i-1][0];
			d[m-i-1][0]=1;
		}


		if（m-i			for（int?j=2;j				if（a[m-i][j-2]>=a[m-i][j-1]&&a[m-i][j-2]>=a[m-i][j]）{???//若第m-i行的第j-2個樹樁上的鉆石價值大于第j-1和第j個樹樁上的鉆石價值（連續的三個樹樁）..
				??b=a[m-i][j-2];????????????????????????????????????????//..就取第j-2個樹樁..
				??d[m-i-1][j-1]=j-2;?????????????????????????????????????//..將樹樁的位置存放到數組d[m-i-1][j-1]中表示當小丑處在第m-i-1行第j-1個樹樁上時，下一步跳上的樹樁的列數，以下類似
				}
				else?if（a[m-i][j-1]>=a[m-i][j-2]&&a[m-i][j-1]>=a[m-i][j]）{
				??b=a[m-i][j-1];
				??d[m-i-1][j-1]=j-1;
				}
				else{
				???b=a[m-i][j];
				??d[m-i-1][j-1]=j;
				}?
			????a[m-i-1][j-1]=b+a[m-i-1][j-1];
			}
		}
		else{???????//與上方的?if（m-i=n，行數大于列數的情況
		//由于行數大于列數，此時除了考慮第0列的邊界情況，還要考慮最后一列的邊界情況.
		//處在第n-1列時，下一步可能跳上的只可能是第n-1列和第n列，比較第m-i行這兩列的值的大小并把較大者與a[m-i-1][n-1]上的數值相加存放在a[m-i-1][n-1]中
			if（a[m-i][n-2]>=a[m-i][n-1]）{????
			???a[m-i-1][n-1]=a[m-i][n-2]+a[m-i-1][n-1];
			???d[m-i-1][n-1]=n-2;
			}
			else{
			????a[m-i-1][n-1]=a[m-i][n-1]+a[m-i-1][n-1];
			????d[m-i-1][n-1]=n-1;
			}

			//以下步驟同行數不大于列數的情況
			for（int?j=2;j			???if（a[m-i][j-2]>=a[m-i][j-1]&&a[m-i][j-2]>=a[m-i][j]）{
				??b=a[m-i][j-2];
				??d[m-i-1][j-1]=j-2;
				}
				else?if（a[m-i][j-1]>=a[m-i][j-2]&&a[m-i][j-1]>=a[m-i][j]）{
				??b=a[m-i][j-1];
				??d[m-i-1][j-1]=j-1;
				}
				else{
				???b=a[m-i][j];
				??d[m-i-1][j-1]=j;
				}?
			????a[m-i-1][j-1]=b+a[m-i-1][j-1];	
		????}??
		}
	}

	int?*e?=?new?int[m];??
	for（int?i=0;i			e[i]=0;

	
	ofstream?outfile;
	outfile.open（“..\\output.txt“）;??//打開輸出文件

	outfile<	for（int?i=1;i		e[i]=d[i-1][e[i-1]];
		outfile<	}

	cout<	outfile.close（）;
	
}

void?main（）
{
?int?data;
?int?i=0j=0;
???????????
?fstream?infile;
?infile.open（“..\\test.txt“ios::in）;??//打開源文件

?if（!infile）
?{
??cerr<<“File?could?not?open.“;
??return;
?}?????????????????????????????

?int?mn;
?infile>>data;????//讀入行數
?m=data;
?infile>>data;???//讀入列數
?n=data;


?//為原始二維數組a開辟空間
?int?**a?=?new?int*[m];??
?for（int?i=0;?i???a[i]?

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2013-06-05?20:23??algorithm\
?????目錄???????????0??2013-06-04?21:30??algorithm\algorithm\
?????文件?????9523200??2013-06-05?20:23??algorithm\algorithm.sdf
?????文件?????????894??2013-05-22?14:43??algorithm\algorithm.sln
?????文件???????10752??2013-06-05?20:23??algorithm\algorithm.suo
?????文件????????3896??2013-06-04?21:32??algorithm\algorithm\algorithm.cpp
?????文件????????4403??2013-06-04?21:07??algorithm\algorithm\algorithm.vcxproj
?????文件????????1313??2013-05-22?14:43??algorithm\algorithm\algorithm.vcxproj.filters
?????文件?????????143??2013-05-22?14:43??algorithm\algorithm\algorithm.vcxproj.user
?????目錄???????????0??2013-08-20?21:22??algorithm\algorithm\Debug\
?????文件????????1567??2013-05-22?14:43??algorithm\algorithm\ReadMe.txt
?????文件?????????214??2013-05-22?14:43??algorithm\algorithm\stdafx.cpp
?????文件?????????233??2013-05-22?14:43??algorithm\algorithm\stdafx.h
?????文件?????????236??2013-05-22?14:43??algorithm\algorithm\targetver.h
?????文件????????1539??2013-05-28?22:06??algorithm\algorithm\test.txt
?????目錄???????????0??2013-06-04?21:32??algorithm\Debug\
?????文件??????684544??2013-06-04?21:31??algorithm\Debug\algorithm.exe
?????文件?????1701256??2013-06-04?21:31??algorithm\Debug\algorithm.ilk
?????文件?????2935808??2013-06-04?21:31??algorithm\Debug\algorithm.pdb
?????文件??????955866??2013-06-04?21:32??algorithm\Debug\Debug.rar
?????目錄???????????0??2013-06-05?19:39??algorithm\ipch\
?????目錄???????????0??2013-06-05?19:39??algorithm\ipch\algorithm-894a63aa\
?????文件?????2359296??2013-06-05?19:39??algorithm\ipch\algorithm-894a63aa\algorithm-915631f3.ipch
?????文件?????????557??2013-06-04?21:32??algorithm\output.txt
?????文件????????1539??2013-05-28?22:06??algorithm\test.txt