sd.cpp

intel线程挑战赛 矩阵转置 快速转置 多线程 tbb 并行算法

#include "iostream.h"
#include "conio.h"
#include "stdlib.h"
#include "time.h"
#include "stdio.h"

struct item{
	int x;
	int y;
	int value;
	item* pNext;
};

// 初始化矩阵数组
void initArray(int mArray[][9]);
// 初始化候选数组
void initItemArray(item* iArray[][9]);
// 输出数组
void printArray(int mArray[][9]);
// 返回候选
item* getRemain(int row, int col, int mArray[][9], int &n);
// 深度优先求解（回溯）
void DF_Solving(int mArray[][9]);
//
void JG_Proc()
{
	item *iArray[9][9];
	int nArray[9][9];
	//
}

void main()
{
	int mArray[9][9];// matrix
	//
	initArray(mArray);
	//
	srand((unsigned)time(NULL));
	//
	DF_Solving(mArray);
	//
	printArray(mArray);
	getch();
}

// 初始化矩阵数组
void initArray(int mArray[][9])
{
	FILE *f = fopen("data.txt", "r");
	if (f)
	{
		int n=0;
		while (fscanf(f, "%d", &mArray[n/9][n%9]) != EOF && n<81)
		{
			n++;
		}
		fclose(f);
	}
	else
	{
		for (int i=0; i<9; i++)
			for (int j=0; j<9; j++)
				mArray[i][j] = 0;
	}
}

// 初始化候选数组
void initItemArray(item* iArray[][9])
{
	for (int i=0; i<9; i++)
		for (int j=0; j<9; j++)
			iArray[i][j] = NULL;
}

// 输出数组
void printArray(int mArray[][9])
{
	for (int i=0; i<9; i++)
	{
		for (int j=0; j<9; j++)
			cout << mArray[i][j] << " ";
		cout << endl;
	}
}

// 返回最小化数组
item* getRemain(int row, int col, int mArray[][9], int &n)
{
	int tArray[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
	int sArray[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};// 记录后面九宫中已经出现的数字
	int count = 0;
	for (int i=0; i<9; i++)
	{
		tArray[mArray[row][i]] = 0;// 去除所在行的数据
		tArray[mArray[i][col]] = 0;// 去除所在列的数据
		// 
		tArray[mArray[row/3*3+i/3][col/3*3+i%3]] = 0;// 去除九宫中的数据
	}
	
	// 随机化
	for (i=0; i<=9; i++)
	{
		int x = rand() % 10;
		int y = rand() % 10;
		
		if (x == y)
			continue;
		
		tArray[x] = tArray[x]+tArray[y];
		tArray[y] = tArray[x]-tArray[y];
		tArray[x] = tArray[x]-tArray[y];
	}
	
	item *iTmp=NULL;
	for (int j=0; j<=9; j++)
	{
		if (tArray[j])
		{
			item* t = new item();
			t->x = row;
			t->y = col;
			t->value = tArray[j];
			t->pNext = iTmp;
			iTmp = t;
			count++;
		}
	}
	
	n = count;
	
	return iTmp;
}

// 深度优先求解（回溯）
void DF_Solving(int mArray[][9])
{
	int n = 0;
	int direction = 1;// 1前行, -1后退
	item *iArray[9][9], *p;
	
	initItemArray(iArray);
	
	for (int i=0; i<81; i++)
	{
		if (mArray[i/9][i%9] && !iArray[i/9][i%9])
		{
			if (direction == 1)
				continue;
			else if (direction == -1)
			{
				i -= 2;
				continue;
			}
		}
		
		direction = 1;
		
		if (iArray[i/9][i%9])
		{
			p = iArray[i/9][i%9];
			iArray[i/9][i%9] = iArray[i/9][i%9]->pNext;
			
			delete p;
			
			if (iArray[i/9][i%9])
			{
				mArray[i/9][i%9] = iArray[i/9][i%9]->value;
			}
			else
			{
				mArray[i/9][i%9] = 0;
				i -= 2;
				direction = -1;
				continue;
			}
		}
		else
		{
			iArray[i/9][i%9] = getRemain(i/9, i%9, mArray, n);
			if (n)
			{
				mArray[i/9][i%9] = iArray[i/9][i%9]->value;
			}
			else
			{
				i -= 2;
				direction = -1;
				continue;
			}
		}
		
		//system("cls");
		//printArray(mArray);
		//cout << endl;
	}
}