#include<iostream>
using namespace std;

//用于存儲點的位置
struct pos
{
	int x;
	int y;
};

//核心處理算法
//angle：存儲數字三角
//min：存儲最小路徑值
//pre: 存儲取得最小路徑的軌跡
void digitTriangle(int **angle, int **min, pos **pre, int n)
{
	int i, j, k;
	int temp;
	int less;

	if(n == 1)
	{
		return angle[1][1];
	}

	for(i = 1; i <= n; i++)
	{
		for(j = 1; j <= i; j++)
		{
			if(min[i-1][j] < min[i-1][j-1])
			{
				less = min[i-1][j] < min[i-1][j-1];
				pre[i][j].x = i-1;
				pre[i][j].y = j;
			}
			else
			{
				less = min[i-1][j-1];
				pre[i][j].x = i-1;
				pre[i][j].y = j-1;
			}
			temp = angle[i][j] + less;
			if(temp < min[i][j])
			{
				min[i][j] = temp;
			}
		}
	}
}

//設從頂到底部的最短路徑為angle[1][1]到angle[i][j]之間的一條論經，打印該路徑的軌跡
void printPath(pos **pre, int i, int j)
{
	int k;
	int x = i;
	int y = j;
	for(k = 1; k < n; k++)
	{
		cout<< x <<","<< y <<endl;
		x = pre[x][y].x;
		y = pre[x][y].y;
	}
}