goldcoinarray.cpp

GoldCoinArray 数据结构与算法 金币阵列问题

// GoldCoinArray.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <vector>

struct S_GCArr
{
	S_GCArr()
	{
		nRowCount = 0;
		nColCount = 0;
		nCount = 0;
		memset(snSrc, 0, sizeof(snSrc));
		memset(snDest, 0, sizeof(snDest));
	}

	int snSrc[100][100];
	int snDest[100][100];
	int nCount;
	int nRowCount;
	int nColCount;
};
typedef std::vector<S_GCArr> S_GCArrList;


int main(int argc, char* argv[])
{
	S_GCArrList gcArrList;
	
	FILE * fpSrc = NULL;
	fpSrc = fopen("input.txt", "r");
	if (fpSrc == NULL)
	{
		printf("open input.txt file failed.\n");
		return 0;
	}

	// 读取文件
	int i;
	int j;
	int k;
	int nArrCount = 0;
	fscanf(fpSrc, "%d\n", &nArrCount);

	for (i = 0; i < nArrCount; i++)
	{
		S_GCArr gcArr;
		fscanf(fpSrc, "%d %d\n", &gcArr.nRowCount, &gcArr.nColCount);

		for (j = 0; j < gcArr.nRowCount; j++)
		{
			for (k = 0; k < gcArr.nColCount; k++)
			{
				if (k == 0)
					fscanf(fpSrc, "%d", &(gcArr.snSrc[j][k]));
				else
					fscanf(fpSrc, " %d", &(gcArr.snSrc[j][k]));
			}
			fscanf(fpSrc, "\n");
		}

		for (j = 0; j < gcArr.nRowCount; j++)
		{
			for (k = 0; k < gcArr.nColCount; k++)
			{
				if (k == 0)
					fscanf(fpSrc, "%d", &(gcArr.snDest[j][k]));
				else
					fscanf(fpSrc, " %d", &(gcArr.snDest[j][k]));
			}
			fscanf(fpSrc, "\n");
		}

		gcArrList.push_back(gcArr);
	}
	fclose(fpSrc);
	
	// 显示文件内容
	printf("--------------------------------------------\n");
	printf("==> input.txt\n");
	printf("%d\n", gcArrList.size());
	for (i = 0; i < gcArrList.size(); i++)
	{
		printf("%d %d\n", gcArrList[i].nRowCount, gcArrList[i].nColCount);

		for (j = 0; j < gcArrList[i].nRowCount; j++)
		{
			for (k = 0; k < gcArrList[i].nColCount; k++)
			{
				if (k == 0)
					printf("%d", gcArrList[i].snSrc[j][k]);
				else
					printf(" %d", gcArrList[i].snSrc[j][k]);
			}
			printf("\n");
		}

		for (j = 0; j < gcArrList[i].nRowCount; j++)
		{
			for (k = 0; k < gcArrList[i].nColCount; k++)
			{
				if (k == 0)
					printf("%d", gcArrList[i].snDest[j][k]);
				else
					printf(" %d", gcArrList[i].snDest[j][k]);
			}
			printf("\n");
		}
	}

	// 计算
	for (i = 0; i < gcArrList.size(); i++)
	{
		// 行转换
		for (j = 0; j < gcArrList[i].nRowCount; j++)
		{
			for (k = 0; k < gcArrList[i].nColCount; k++)
			{
				if (gcArrList[i].snSrc[j][k] == gcArrList[i].snDest[j][k])
					break;
			}
			if (k == gcArrList[i].nColCount)
			{
				for (k = 0; k < gcArrList[i].nColCount; k++)
					gcArrList[i].snSrc[j][k] = gcArrList[i].snDest[j][k];
				gcArrList[i].nCount++;
			}
		}

		// 列转换
		for (k = 0; k < gcArrList[i].nColCount; k++)
		{
			for (j = 0; j < gcArrList[i].nRowCount; j++)
			{
				if (gcArrList[i].snSrc[j][k] != gcArrList[i].snDest[j][k])
					break;
			}
			if (j == gcArrList[i].nRowCount)
				continue;

			// 搜索可交换的列
			int p;
			for (p = k + 1; p < gcArrList[i].nColCount; p++)
			{
				for (j = 0; j < gcArrList[i].nRowCount; j++)
				{
					if (gcArrList[i].snSrc[j][p] != gcArrList[i].snDest[j][k])
						break;
				}
				if (j == gcArrList[i].nRowCount)
					break;
			}
			if (p == gcArrList[i].nColCount)
				break; // 未找到

			// 进行交换
			for (j = 0; j < gcArrList[i].nRowCount; j++)
			{
				int nTemp = gcArrList[i].snSrc[j][k];
				gcArrList[i].snSrc[j][k] = gcArrList[i].snSrc[j][p];
				gcArrList[i].snSrc[j][p] = nTemp;
			}
			gcArrList[i].nCount++;
		}

		// 判断是否转换成功
		for (j = 0; j < gcArrList[i].nRowCount; j++)
		{
			for (k = 0; k < gcArrList[i].nColCount; k++)
			{
				if (gcArrList[i].snSrc[j][k] != gcArrList[i].snDest[j][k])
					break;
			}
		}
		if (k != gcArrList[i].nColCount)
			gcArrList[i].nCount = -1; // 转换不成功则为-1
	}

	// 输出结果
	printf("\n");
	printf("--------------------------------------------\n");
	printf("==> output.txt\n");

	for (i = 0; i < gcArrList.size(); i++)
		printf("%d\n", gcArrList[i].nCount);

	// 输出到文件
	FILE * fpDest = NULL;
	fpDest = fopen("output.txt", "w");
	if (fpDest == NULL)
	{
		printf("open or create output.txt file failed.\n");
		return 0;
	}

	for (i = 0; i < gcArrList.size(); i++)
		fprintf(fpDest, "%d\n", gcArrList[i].nCount);
	fclose(fpDest);

	// 结束
	printf("\n");
	printf("--------------------------------------------\n");
	printf("press any key to exit.\n");
	getch();

	return 0;
}