首页 > 搜索 > DFS搜索 > hdu 1929 A Puzzling Problem-模拟-[解题报告]C++
2013
12-26

hdu 1929 A Puzzling Problem-模拟-[解题报告]C++

A Puzzling Problem

问题描述 :

Anna Graham is a puzzle maker who prides herself in the quality and complexity of her work. She makes puzzles of all kinds – crosswords, logic problems, acrostics, and word search puzzles, to name but a few. For each puzzle, she has developed a set of rules which she constrains herself to follow. For word search puzzles, she insists not only that all the words be connected to one another (as in most word search puzzles), but also that removing any word from the word list will not cause one or more words to become disconnected from the rest. (Two words are connected if they contain a common letter in the grid.) The example word search puzzle on the left satisfies this condition, but the one on the right does not (removing the word Pascal from the word list disconnects Java from the other two words).

Your job is to write a program that checks to see if Anna’s word search problems are up to snuff.

输入:

Input will consist of multiple test cases. The first line of each test case contains 3 integers n m l, where n and m are the number of rows and columns in the puzzle and l is the number of words. Following this are n lines containing m uppercase characters each (the puzzle) followed by l lines containing one word each (the word list, in mixed case). Each word in the word list will appear in the puzzle exactly once. There will be no more than 100 rows and 100 columns in the puzzle and no more than 100 words to search for. There will be no spaces in the input words.

输出:

Input will consist of multiple test cases. The first line of each test case contains 3 integers n m l, where n and m are the number of rows and columns in the puzzle and l is the number of words. Following this are n lines containing m uppercase characters each (the puzzle) followed by l lines containing one word each (the word list, in mixed case). Each word in the word list will appear in the puzzle exactly once. There will be no more than 100 rows and 100 columns in the puzzle and no more than 100 words to search for. There will be no spaces in the input words.

样例输入:

5 6 3
PBROGR
PASCAL
ASMMIN
GIICON
TCELST
BASIC
LISP
Pascal
5 6 4
PBROJR
PASCAL
ASMMVN
GIICAN
TCELST
BASIC
Java
LISP
Pascal
0 0 0

样例输出:

Yes
No

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

int t;
int n, m;
char map[10][10];
int judge;
int vis[20];
struct Block {
	char set[10][10];
	int num;
	int n, m;
} b[20];

int ju(int ii, int x, int y) {
	int i, j;
	for (i = x; i < x + b[ii].n; i ++)
		for (j = y; j < y + b[ii].m; j ++)
			if (map[i][j] != '0' && b[ii].set[i -x][j - y] != '0')
				return 0;
	return 1;
}
void dfs(int x, int y, int tt, int num) {
	int i, j, k;
	if (tt == t) {
		if (num == 16)
			judge = 1;
		return;
	}
	if (y > 4) {
		if (x < 4)
			dfs(x + 1, 1, tt, num);
		return;
	}
	for (i = 1; i <= t; i ++) {
		if (!vis[i] && ju(i, x, y)) {
			vis[i] = 1;
			for (j = x; j < x + b[i].n; j ++)
				for (k = y; k < y + b[i].m; k ++)
					if (b[i].set[j - x][k - y] != '0')
						map[j][k] = b[i].set[j - x][k - y] + i - 1;
			dfs(x, y + 1, tt + 1, num + b[i].num);
			if (judge) return;
			vis[i] = 0;
			for (j = x; j < x + b[i].n; j ++)
				for (k = y; k < y + b[i].m; k ++)
					if (b[i].set[j - x][k - y] != '0')
						map[j][k] = '0';
		}
	}
	dfs(x, y + 1, tt, num);
}
int main() {
	int i, j, k;
	int bo = 0;
	while (scanf("%d", &t) != EOF && t) {
		if (bo == 0) 
			bo = 1;
		else
			printf("\n");
		judge = 0;
		memset(b, 0, sizeof(b));
		memset(vis, 0, sizeof(vis));
		memset(map, '1', sizeof(map));
		for (i = 1; i <= 4; i ++)
			for (j = 1; j <= 4; j ++)
				map[i][j] = '0';
		for (i = 1; i <= t ; i ++) {
			scanf("%d%d%*c", &n, &m);
			b[i].n = n; b[i].m = m;
			for (j = 0; j < n; j ++) {
				gets(b[i].set[j]);
				int len = strlen(b[i].set[j]);
				for (k = 0; k < len; k ++)
					if (b[i].set[j][k] != '0')
						b[i].num ++;
			}
		}
		dfs(1, 1, 0, 0);
		if (judge) {
			for (i = 1; i <= 4; i ++) {
				for (j = 1; j <= 4; j ++)
					printf("%c", map[i][j]);
				printf("\n");
			}
		}
		else
			printf("No solution possible\n");
	}
	return 0;
}

解题转自:http://blog.csdn.net/accelerator_/article/details/9884353


  1. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n