华为机试

找到它是个小游戏，你需要在一个矩阵中找到给定的单词，假设给定单词HELLOWORLD，在矩阵中只要能找到H->E->L->L->O->W->O->R->L->D连成的单词，就算通过。

注意区分英文字母大小写，并且你只能上下左右行走，不能走回头路。

输入描述：

输入第一行包含两个整数n、m(0<n,m<21),分别表示n行m列的矩阵，第二行时长度不超过100的单词W（在整个矩阵中给定单词只会出现一次），从第三行到到第n+2行时只包含大小写英文字母的长度为m的字符串矩阵。

输出描述：

如果能在矩阵中连成给定的单词，则输出给定单词首字母在矩阵中的位置（第几行 第几列），否则输出“NO”

示例1

输入

5 5

HELLOWORLD

CPUCY

EKLQH

CHELL

LROWO

DGRBC

输出

3 2

解题

#include<stdio.h>
#include<string.h>
#include<malloc.h>
//#pragma region MyRegion
///*
//在矩阵中只要能找到H->E->L->L->O->W->O->R->L->D连成的单词，
//*/
//#pragma endregion
//

const int Max = 5;
char matrix[Max][Max];
char keyword[] = { 'H', 'E', 'L', 'L', 'O', 'W', 'O', 'R', 'L', 'D' };
bool isUsed [Max][Max];
int X=-1;
int Y=-1;

void copy(char*A, char*B,int count){
	for (int i = 0; i < Max; i++)
	{
		{
			A[i] = B[i];
		}
	}
}
void setValue()
{
	char *temp = (char*)malloc(Max*sizeof(char));
	char s0[] = { 'C', 'P', 'U', 'C', 'Y' };
	char s1[] = { 'E', 'K', 'L', 'Q', 'H' };
	char s2[] = { 'C', 'H', 'E', 'L', 'L' };
	char s3[] = { 'L', 'R', 'O', 'W', 'O' };
	char s4[] = { 'D', 'G', 'R', 'B', 'C' };
	copy(matrix[0], s0, Max);
	copy(matrix[1], s1, Max);
	copy(matrix[2], s2, Max);
	copy(matrix[3], s3, Max);
	copy(matrix[4], s4, Max);
	for (int i = 0; i < Max; i++)
	{
		for (int j = 0; j < Max; j++)
		{
			isUsed[i][j] = false;
		}
	
	}
}
void printfMatrix()
{
	printf("\n");
	for (int i = 0; i < Max; i++)
	{
		for (int j = 0; j < Max; j++)
		{
			printf("%c ", matrix[i][j]);
		}
		printf("\n");
	}
}
void printfisUsed()
{
	printf("\n");
	for (int i = 0; i < Max; i++)
	{
		for (int j = 0; j < Max; j++)
		{
			printf("%d", isUsed[i][j]);
		}
		printf("\n");
	}
}

bool find(int i, int j, int keyWordIndex)
{
	int direction[4][2] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
	int ni = i;
	int nj = j;
	isUsed[i][j] = true;
	if (keyWordIndex == strlen(keyword)-1 && matrix[i][j] == keyword[keyWordIndex])
	{
		bool falg = false;
		for (int i = 0; i < Max; i++)
		{
			for (int j = 0; j < Max; j++)
			{
				if (isUsed[i][j] == true)
				{
					if (!falg)
					{
						X = i;
						Y = j;
					}
					falg = true;
				}
			}
		}
		return true;
	}
	if (matrix[i][j] == keyword[keyWordIndex])
	{
		printfisUsed();
		for (int i = 0; i < 4; i++)
		{
			int tempi = ni + direction[i][0];
			int tempj = nj + direction[i][1];
			if (tempi >= 0 && tempi<Max && tempj >= 0 && tempj < Max && isUsed[tempi][tempj] == false)
			{
				find(tempi, tempj, keyWordIndex + 1);
			}
		}
	}
	isUsed[i][j] = false;
	return false;

}

int main()
{
	setValue();
	printfMatrix();
	for (int i = 0; i < Max; i++)
	{
		for (int j = 0; j < Max; j++)
		{
			find(i, j, 0);
		}
	}
	printf("%d %d", X, Y);
	return 0;
}