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

#define MAXSIZE 1024

struct Result
{
	int i ;
	int j ;
	int direct ;
} ;


const int direction[8][2] = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}} ;  
char	table[MAXSIZE][MAXSIZE] ;
char	word[MAXSIZE][MAXSIZE] ;
Result	result[MAXSIZE] ;
int		M, N ;



struct TrieNode
{
	bool		isWord ;
	bool		visited ;
	int			id ;
	TrieNode*	next[26] ;
	TrieNode ()
	{
		isWord = visited = false ;
		id = -1 ;
		int	i ;
		for (i = 0 ; i < 26 ; i++)
			next[i] = NULL ;
	}
} ;

void Insert (TrieNode *&root, char target[], int ID)
{
	int			i, len = strlen (target) ;
	TrieNode	*current ;

	while (target[len - 1] == ' ')	len-- ;

	if (root == NULL)
		root = new TrieNode () ;

	current = root ;
	
	for (i = 0 ; i < len ; i++)
	{
		if (current->next[target[i] - 'A'] == NULL)
			current->next[target[i] - 'A'] = new TrieNode () ;
		current = current->next[target[i] - 'A'] ;
		if (i == len - 1)
		{
			current->isWord = true ;
			current->id = ID ;
		}
	}
}

bool LegalPos (int i, int j)
{
	return 0 <= i && i < M && 0 <= j && j < N ;
}

bool Search (TrieNode *current, int i, int j, int k, int &ID)
{
	if (!LegalPos (i,j) || current->next[table[i][j] - 'A'] == NULL)
		return false ;

	current = current->next[table[i][j] - 'A'] ;

	if (current->isWord == true && current->visited == false)
	{
		ID = current->id ;
		current->visited = true ;
		return true ;
	}

	i += direction[k][0] ;
	j += direction[k][1] ;

	return Search (current, i, j, k, ID) ;
}

void Research (TrieNode * root, int i, int j, int k, int &ID)
{
	if (Search (root, i, j ,k, ID))
	{
		result[ID].i = i ;
		result[ID].j = j ;
		result[ID].direct = k ;
		Research (root, i, j, k, ID) ;
	}
}


int main ()
{
	memset (result, -1, sizeof (result)) ;
	int		 W, i, j, k, ID ;
	TrieNode *root = NULL ;
	
	scanf ("%d%d%d", &M, &N, &W) ;
	//getchar () ;
	fflush (stdin) ;

	for (i = 0 ; i < M ; i++)
		gets (table[i]) ;

	for (i = 0 ; i < W ; i++)
	{
		gets (word[i]) ;
		Insert (root, word[i], i) ;
	}

	for (i = 0 ; i < M ; i++)
		for (j = 0 ; j < N ; j++)
			for (k = 0 ; k < 8 ; k++)
				Research (root, i, j, k, ID) ;

	for (i = 0 ; i < W ; i++)
		printf ("%d %d %c\n", result[i].i, result[i].j, result[i].direct + 'A') ;


	return 0 ;
}

• Re:Discuss所有数据都过了！还是WA！难道是输入输出处理有问题？本人用trie做，附代码，望大家指点啊！ (35) ss08zhangchi 2010-01-27 20:48:04