2118.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2118 on 2005-12-29 at 18:24:47 */ 
#include <cstdio>
#include <cstring>
#include <cstdlib>

const int SIZE = 5;
const int MAX = 5120;
const int L_MAX = 32;

char map[SIZE][SIZE];
bool used[SIZE][SIZE];

int DFS(char*, int, int, int, int);
int cmp(const void*, const void*);

int main()
{
	int n, i;
	int wl[MAX];
	char word[MAX][L_MAX];
	
	for(n = 0; gets(word[n]) != NULL; n++) {
		if(!strcmp(word[n], "*")) break;
		else if(word[n][0] == 0) n--;
	}
	qsort(word, n, sizeof(word[0]), cmp);
	for(i = 0; i < n; i++) wl[i] = strlen(word[i]);
	while(true) {
		for(i = 0; i < SIZE; i++) {
			if(gets(map[i]) == NULL) return 0;
			else if(map[i][0] == 0) i--;
		}
		for(i = 0; i < n; i++) {
			if(wl[i] > SIZE*SIZE) continue;
			else {
				int r = 0, x, y, j;
				memset(used, false, sizeof(used));
				for(x = 0; x < SIZE; x++) {
					for(y = 0; y < SIZE; y++) {
						r += DFS(word[i], wl[i], 0, x, y);
					}
				}
				for(j = 0; j < r; j++) printf("%s\n", word[i]);
			}
		}
	}
	
	return 0;
}

int DFS(char* w, int l, int cl, int x, int y)
{
	if(used[x][y] || map[x][y] != w[cl]) return 0;
	else if(cl == l-1) return 1;
	else {
		int r = 0;
		used[x][y] = true;
		if(x != 0) 				   	   r += DFS(w, l, cl+1, x-1, y);
		if(x != SIZE-1) 			   r += DFS(w, l, cl+1, x+1, y);
		if(y != 0) 				   	   r += DFS(w, l, cl+1, x, y-1);
		if(y != SIZE-1)     		   r += DFS(w, l, cl+1, x, y+1);
		if(x != 0 && y != 0)       	   r += DFS(w, l, cl+1, x-1, y-1);
		if(x != 0 && y != SIZE-1)      r += DFS(w, l, cl+1, x-1, y+1);
		if(x != SIZE-1 && y != 0)      r += DFS(w, l, cl+1, x+1, y-1);
		if(x != SIZE-1 && y != SIZE-1) r += DFS(w, l, cl+1, x+1, y+1);
		used[x][y] = false;
		return r;
	}
}
int cmp(const void* a, const void* b)
{
	return strcmp((char*)a, (char*)b);
}