APCS程式檢測 -實作題1050305 第4題 血緣關係(進階思考)

APCS程式檢測 -實作題1050305 第4題 血緣關係(進階思考)

上一篇
APCS程式檢測 -實作題1050305 第4題 血緣關係
https://husking-studio.com/apcs-1050305-4/

試著印出路徑看看
加入 PrintPath 相關程式碼

完整程式碼

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

//樹的基本結構和功能
void AddChild(int** pTree, int nRow, int nCol, int nParent, int nChild);	//加入節點
int GetLeafNum(int** pTree, int nRow, int nCol);	//取得葉子節點的數量
int FindRoot(int** pTree, int nRow, int nCol);		//找出根節點
int GetChildNum(int** pTree, int nRow, int nCol, int nNode);	//取得某節點的孩子數量
int Distance(int** pTree, int nRow, int nCol, int nNode);	//取得某節點的高度
void PrintTree(int** pTree, int nRow, int nCol);	//印出

//
void SetLeaf(int** pTree, int nRow, int nCol, int* pLeaf);
void SetParent(int** pTree, int nRow, int nCol, int** pParentTree, int nParentRow, int nParentCol);
void FindParent(int** pTree, int nRow, int nCol, int nChild, int* pParent, int nParentRow, int nParentCol, int k);
int GetMaxDistance(int** pParentTree, int nParentRow, int nParentCol, int* pLeaf, int nLeafNum);
int GetPairDistance(int** pParentTree, int nParentRow, int nParentCol, int nA, int nB);

//印出路徑相關
void PrintPath(int** pTree, int nRow, int nCol, int** pParentTree, int nParentRow, int nParentCol, int* pLeaf, int nLeafNum);
int GetMaxDistance2(int** pParentTree, int nParentRow, int nParentCol, int* pLeaf, int nLeafNum, int* nA, int* nB);
int GetPairDistance2(int** pParentTree, int nParentRow, int nParentCol, int nA, int nB, int* nParent);

int main()
{
	//處理輸入-n個節點
	string strInput;
	getline(cin, strInput);
	int n = stoi(strInput);

	//
	int* pChildNum = new int[n];
	for (int i = 0; i < n; i++)
		pChildNum[i] = 0;

	//將接下來的輸入存在 vector 裡
	vector<string> vecInput;
	for (int i = 0; i < (n - 1); i++)
	{
		int nParentNode = -1;
		getline(cin, strInput);

		stringstream delim(strInput);
		string pch;

		getline(delim, pch, ' ');
		nParentNode = stoi(pch);

		getline(delim, pch, ' ');

		pChildNum[nParentNode]++;
		vecInput.push_back(strInput);
	}
	//
	int nMaxChildNum = 0;
	for (int i = 0; i < n; i++)
	{
		if (pChildNum[i] > nMaxChildNum)
			nMaxChildNum = pChildNum[i];
	}

	delete[] pChildNum;

	//
	int nTreeRow = n;
	int nTreeCol = nMaxChildNum;

	//宣告
	int** pTree;
	pTree = new int* [nTreeRow];
	for (int i = 0; i < nTreeRow; i++)
		pTree[i] = new int[nTreeCol];

	//初始化
	for (int i = 0; i < nTreeRow; i++)
		for (int j = 0; j < nTreeCol; j++)
			pTree[i][j] = -1;

	//加入資料
	for (int i = 0; i < (int)vecInput.size(); i++)
	{
		int nParentNode = -1;
		int nChildNode = -1;

		stringstream delim(vecInput[i]);
		string pch;

		getline(delim, pch, ' ');
		nParentNode = stoi(pch);

		getline(delim, pch, ' ');
		nChildNode = stoi(pch);

		AddChild(pTree, nTreeRow, nTreeCol, nParentNode, nChildNode);
	}

	//找葉子節點，存在 pLeaf 陣列裡
	int nLeafNum = GetLeafNum(pTree, nTreeRow, nTreeCol);
	int* pLeaf = new int[nLeafNum];
	SetLeaf(pTree, nTreeRow, nTreeCol, pLeaf);

	//找根節點
	int nRoot = FindRoot(pTree, nTreeRow, nTreeCol);
	//深度
	int nDepth = Distance(pTree, nTreeRow, nTreeCol, nRoot);

	//父連結
	int nParentTreeRow = nTreeRow;
	int nParentTreeCol = nDepth;

	//建立父連結資料
	int** pParentTree;
	pParentTree = new int* [nParentTreeRow];
	for (int i = 0; i < nParentTreeRow; i++)
		pParentTree[i] = new int[nParentTreeCol];

	//初始化
	for (int i = 0; i < nParentTreeRow; i++)
		for (int j = 0; j < nParentTreeCol; j++)
			pParentTree[i][j] = -1;

	//建立父連結陣列
	SetParent(pTree, nTreeRow, nTreeCol, pParentTree, nParentTreeRow, nParentTreeCol);

	//印出路徑
	PrintPath(pTree, nTreeRow, nTreeCol, pParentTree, nParentTreeRow, nParentTreeCol, pLeaf, nLeafNum);

	//delete
	for (int i = 0; i < nParentTreeRow; i++)
		delete[] pParentTree[i];
	delete[] pParentTree;
	delete[] pLeaf;
	for (int i = 0; i < nTreeRow; i++)
		delete[] pTree[i];
	delete[] pTree;

	system("pause");
	return 0;
}
int GetPairDistance(int** pParentTree, int nParentRow, int nParentCol, int nA, int nB)
{
	int* pRowA = pParentTree[nA];
	int* pRowB = pParentTree[nB];
	int nMaxDistance = 0;
	int nTempDistance = 0;

	int a2 = 0;
	int b2 = 0;

	bool bFind = false;

	for (int a = 0; a < nParentCol; a++)
	{
		for (int b = 0; b < nParentCol; b++)
		{
			if (pRowA[a] == pRowB[b])		//找共同父節點
			{
				a2 = a + 1;
				b2 = b + 1;

				bFind = true;
				break;
			}
		}
		if (bFind)
			break;
	}

	if (bFind)
	{
		nTempDistance = a2 + b2;
		if (nTempDistance > nMaxDistance)
			nMaxDistance = nTempDistance;
	}

	return nMaxDistance;
}
int GetMaxDistance(int** pParentTree, int nParentRow, int nParentCol, int* pLeaf, int nLeafNum)
{
	int nMaxDistance = 0;
	int nTempDistance = 0;

	//在葉子節點中捉對
	for (int i = 0; i < nLeafNum; i++)
	{
		for (int j = i + 1; j < nLeafNum; j++)
		{
			nTempDistance = GetPairDistance(pParentTree, nParentRow, nParentCol, pLeaf[i], pLeaf[j]);
			if (nTempDistance > nMaxDistance)
				nMaxDistance = nTempDistance;
		}
	}
	return nMaxDistance;
}
void SetParent(int** pTree, int nRow, int nCol, int** pParentTree, int nParentRow, int nParentCol)
{
	int k = 0;
	for (int i = 0; i < nRow; i++)
	{
		k = 0;
		FindParent(pTree, nRow, nCol, i, pParentTree[i], nParentRow, nParentCol, k);
	}
}
void FindParent(int** pTree, int nRow, int nCol, int nChild, int* pParent, int nParentRow, int nParentCol, int k)
{
	bool bFind = false;
	for (int i = 0; i < nRow; i++)
	{
		for (int j = 0; j < nCol; j++)
		{
			if (pTree[i][j] == nChild)
			{
				bFind = true;
				pParent[k] = i;
				FindParent(pTree, nRow, nCol, i, pParent, nParentRow, nParentCol, k + 1);
			}
		}
	}
	if (bFind == false)
		return;
}
void SetLeaf(int** pTree, int nRow, int nCol, int* pLeaf)
{
	int k = 0;
	bool bAll = true;

	for (int i = 0; i < nRow; i++)
	{
		bAll = true;
		for (int j = 0; j < nCol; j++)
		{
			if (pTree[i][j] != -1)
			{
				bAll = false;
				break;
			}
		}
		if (bAll)
		{
			pLeaf[k] = i;
			k++;
		}
	}
}
//取得某節點的高度
int Distance(int** pTree, int nRow, int nCol, int nNode)
{
	int nChildNum = GetChildNum(pTree, nRow, nCol, nNode);
	if (nChildNum == 0)
		return 0;

	int nDepthMax = 0;
	int nDepth = 0;
	int* pRow = pTree[nNode];
	for (int k = 0; k < nChildNum; k++)
	{
		nDepth = Distance(pTree, nRow, nCol, pRow[k]) + 1;
		if (nDepth > nDepthMax)
			nDepthMax = nDepth;
	}
	return nDepthMax;
}
//取得某節點的孩子數量
int GetChildNum(int** pTree, int nRow, int nCol, int nNode)
{
	int nChildNum = 0;
	int* pRow = pTree[nNode];

	for (int j = 0; j < nCol; j++)
	{
		if (pRow[j] != -1)
			nChildNum++;
	}
	return nChildNum;
}
//取得葉子節點的數量
int GetLeafNum(int** pTree, int nRow, int nCol)
{
	int nLeafNum = 0;
	bool bHaveChild = false;

	for (int i = 0; i < nRow; i++)
	{
		bHaveChild = false;
		for (int j = 0; j < nCol; j++)
		{
			if (pTree[i][j] != -1)
			{
				bHaveChild = true;
				break;
			}
		}
		if (bHaveChild == false)
			nLeafNum++;
	}
	return nLeafNum;
}
//找出根節點
int FindRoot(int** pTree, int nRow, int nCol)
{
	bool* bNode = new bool[nRow];
	for (int i = 0; i < nRow; i++)
		bNode[i] = false;

	for (int i = 0; i < nRow; i++)
	{
		for (int j = 0; j < nCol; j++)
		{
			if (pTree[i][j] != -1)
				bNode[pTree[i][j]] = true;
		}
	}

	int nRoot = -1;
	for (int i = 0; i < nRow; i++)
	{
		if (bNode[i] == false)
		{
			nRoot = i;
			break;
		}
	}

	delete[] bNode;

	return nRoot;
}
//加入節點
void AddChild(int** pTree, int nRow, int nCol, int nParent, int nChild)
{
	int* pRow = pTree[nParent];

	for (int j = 0; j < nCol; j++)
	{
		if (pRow[j] == -1)
		{
			pRow[j] = nChild;
			break;
		}
	}
}
//印出
void PrintTree(int** pTree, int nRow, int nCol)
{
	for (int i = 0; i < nRow; i++)
	{
		cout << "node(" << i << ")->";
		for (int j = 0; j < nCol; j++)
		{
			cout << pTree[i][j] << " ";
		}
		cout << endl;
	}
}
void PrintPath(int** pTree, int nRow, int nCol, int** pParentTree, int nParentRow, int nParentCol, int* pLeaf, int nLeafNum)
{
	//取得最遠的葉子節點距離
	int nA = -1;	//最遠的葉子節點1
	int nB = -1;	//最遠的葉子節點2
	GetMaxDistance2(pParentTree, nParentRow, nParentCol, pLeaf, nLeafNum, &nA, &nB);

	//
	int nParent = -1;	//共同的父節點
	int nDistance = GetPairDistance2(pParentTree, nParentRow, nParentCol, nA, nB, &nParent);

	//
	cout << nA << "->";
	int* pA = pParentTree[nA];
	for (int j = 0; j < nParentCol; j++)
	{
		cout << pA[j] << "->";
		if (pA[j] == nParent)
			break;
	}

	//
	int* pB = pParentTree[nB];
	bool bPrint = false;
	for (int j = (nParentCol - 1); j >= 0; j--)
	{
		if (bPrint)
			cout << pB[j] << "->";

		if (pB[j] == nParent)
			bPrint = true;
	}
	cout << nB << endl;
}
int GetMaxDistance2(int** pParentTree, int nParentRow, int nParentCol, int* pLeaf, int nLeafNum, int* nA, int* nB)
{
	int nMaxDistance = 0;
	int nTempDistance = 0;

	//在葉子節點中捉對
	for (int i = 0; i < nLeafNum; i++)
	{
		for (int j = i + 1; j < nLeafNum; j++)
		{
			nTempDistance = GetPairDistance(pParentTree, nParentRow, nParentCol, pLeaf[i], pLeaf[j]);
			if (nTempDistance > nMaxDistance)
			{
				*nA = pLeaf[i];
				*nB = pLeaf[j];
				nMaxDistance = nTempDistance;
			}
		}
	}
	return nMaxDistance;
}
int GetPairDistance2(int** pParentTree, int nParentRow, int nParentCol, int nA, int nB, int* nParent)
{
	int* pRowA = pParentTree[nA];
	int* pRowB = pParentTree[nB];
	int nMaxDistance = 0;
	int nTempDistance = 0;

	int a2 = 0;
	int b2 = 0;

	bool bFind = false;

	for (int a = 0; a < nParentCol; a++)
	{
		for (int b = 0; b < nParentCol; b++)
		{
			if (pRowA[a] == pRowB[b])		//找共同父節點
			{
				a2 = a + 1;
				b2 = b + 1;

				*nParent = pRowA[a];

				bFind = true;
				break;
			}
		}
		if (bFind)
			break;
	}

	if (bFind)
	{
		nTempDistance = a2 + b2;
		if (nTempDistance > nMaxDistance)
			nMaxDistance = nTempDistance;
	}

	return nMaxDistance;
}