纵横字谜的答案(Crossword Answer，ACM/ICPC WOrld Finals 1994, UVa 232)

问题描述网址：

点击访问题目

问题中文描述：

       输入一个r行c列（1<=r, c<=10）的网格， 黑格用“*”表示， 每个白格都填有一个字母。如果一个白格的左边相邻位置或者上边相邻位置没有白格（可能是黑格，也可能是网格边界） ， 则称这个白格是一个起始格。

首先把所有起始格按照从上到下，从左到右的顺序编号1， 2， 3，···，如图所示。

      接下来要找出所有横向单词（Across) 。这些单词必须从一个起始格开始，向右延伸到一个黑格的左边或者整个网格的最右列 。 最后找出所有竖向单词 （Down）  。这些单词必须从一个起始格开始，向下延伸到一个黑格的上边或者整个网格的最下行 。 

下面给出样例：

Sample Input

2 2
AT
*O
6 7
AIM*DEN
*ME*ONE
UPON*TO
SO*ERIN
*SA*OR*
IES*DEA
0

Sample Output
puzzle #1:
Across
1.AT
3.O
Down
1.A
2.TO
puzzle #2:
Across
1.AIM
4.DEN
7.ME
8.ONE
9.UPON
11.TO
12.SO
13.ERIN
15.SA
17.OR
18.IES
19.DEA
Down
1.A
2.IMPOSE
3.MEO
4.DO
5.ENTIRE
6.NEON
9.US
10.NE
14.ROD
16.AS
18.I
20.A

个人思路：

代码演示：

# include <iostream>
# include <cstring>
# define maxr 10
# define maxc 10

using namespace std;


bool is_legal(char (*ch)[maxc], int (*sh)[maxc],int i,int j,int &k) {//判断某个数是不是合法的起始格
	if (ch[i][j] != '*') {
		if (i == 0 || j == 0) {//左上边界定为起始格
			sh[i][j] = k++;
			return true;
		}
		else if (ch[i-1][j]=='*'||ch[i][j-1]=='*') {
			sh[i][j] = k++;
			return true;
		}
		else //是白格但非起始格，标记为-1
			sh[i][j] = -1;
	}
	else//   '*'
		return false;
}
int main() {
	int r, c;
	int i = 0;
	int count = 0;
	while (scanf("%d%d", &r, &c) == 2) {
		if (count)
			printf("\n");
		char s[maxr][maxc];
		int d[maxr][maxc];//保存某个网格是否是起始格
		memset(d, 0, sizeof(d));
		memset(s, 0, sizeof(s));
		//input grids
		for (int i = 0; i <r; i++) {
			scanf("%s", s[i]);
		}
		int k = 1;//起始格编号
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				is_legal(s, d, i, j, k);

			}
		}
		
		printf("puzzle #%d:\n", ++i);
		printf("Across");
		for (int i = 0; i < r; i++) {
			int kase = 0;
			for (int j = 0; j < c; j++) {
				
				if (d[i][j]!=0) {
					kase++;
					if (kase==1) //碰到单词第一个字母时输出序号。
						printf("\n%3d.", d[i][j]);
					printf("%c", s[i][j]);//输出字母
				}
				else 
					kase = 0;
			}
		}
		printf("\nDown");
		for (int i = 0; i < r; i++) {

			for (int j = 0; j < c; j++) {
				int k = i;
				int kase = 0;
				while (d[k][j]!=0&&k < r) {//是起始格时，竖向遍历单词，并把d[i][j]==0,即变更为*
					kase++;
					if (kase == 1) 
						printf("\n%3d.", d[k][j]);
					printf("%c", s[k][j]);
					d[k][j] = 0;
					k++;
				}
			}
		}
		printf("\n");
		count++;
	}
	return 0;
}