《算法竞赛入门经典（第2版）》 习题3-6 纵横字谜的答案(Crossword Answers, ACMICPC World Finals 1994, UVa232)

《算法竞赛入门经典（第2版）》 习题3-6 纵横字谜的答案(Crossword Answers, ACM/ICPC World Finals 1994, UVa232)

输入一个r行c列（1<=r，c<=10）的网格，黑格用“*”表示，每个白格都填有一个字母。如果一个白格的左边相邻位置或者上边相邻位置没有白格（可能是黑格，也可能出了网格边界），则称这个白格是一个起始格。首先把所有起始格按照从上到下、从左到右的顺序编号为1，2，3，…，如图3-7所示。接下来要找出所有横向单词（Across）。这些单词必须从一个起始格开始，向右延伸到一个黑格的左边或者整个网格的最右列。最后找出所有竖向单词（Down）。这些单词必须从一个起始格开始，向下延伸到一个黑格的上边或者整个网格的最下行。

输入

每一个字谜网格的输入数据第1行是两个整数r和c，(1 ≤ r ≤ 10 且 1 ≤ c ≤ 10)，r是网格的行数，c是网格的列数。接下来是r行字符，每行的字符都有c个，这些字符描述了网格的构成。这些字符或者是字母，或者是用来表示黑格的’*‘号。全部输入的最后是单独的一行，仅包含一个数字’0’。【注意：输入的不同网格之间没有其它内容分隔】

示例输入

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

示例输出

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

分析

这又是一个模拟题，只要照着题目描述的做即可。值得注意的是，每次准备读入一个网格的数据时，一定要将网格数组清零、起始格数据清零、起始格数量清零，但是不要将网格数量清零。==清零，重要。==然后，就可以愉快的开始读入一个网格的数据了。稳妥起见，可以先读一个r，如果它是0，则结束程序，如果不是0，继续读入c。 接下来，就要逐个记录起始格。可以将第i个起始格的x、y坐标保存在x[i]、y[i]这两个数组中。如果你之前建立网格数组的时候建得比较大，且全部置0了，然后从下标1开始存储——那么现在判断起始格就无需担心数组越界问题，只要一个白格的左边或上边不是白格，就可以记录起始格了。 最后，就要分别输出横向与竖向单词了。输出完毕，不要忘记读取下一个r哟！

代码

#include <stdio.h> #include <string.h> #include <ctype.h> #include <time.h> char a[12][12]; // 存储一个网格的数据 int x[120]; // 存储一个起始格的x坐标，x[1]是第1个起始格的x坐标 int y[120]; // 存储一个起始格的y坐标，y[1]是第1个起始格的y坐标 int r, c, tot=0, heads; // tot计数器存储网格的个数, heads计数器存储起始格的个数 int main() { scanf("%d", &r); // 读入r，或结束标记0 while(r!=0) // 如果不是0，则继续 { memset(a,0,12*12); // 网格数据清零 memset(x,0,120); // 起始格数据清零 memset(y,0,120); // 起始格数据清零 heads = 0; // 起始格数据清零 scanf("%d", &c); // 读入c tot++; printf("\npuzzle #%d\n", tot); // 输出一个网格的抬头（一个空行，然后是编号） //-----------------开始输入一个r行c列的网格内部的数据 char in; int count = 0, i=1, j=1; // 一个网格中的元素计数count，i和j是当前输入的元素在网格中的位置 while(count<r*c) // 输入一个网格的总共r*c个元素 { in = getchar(); // 读入一个字符 if((in>='A' && in<='Z') || in=='*'){ // 如果输入的是大写字母或*号， a[i][j] = in; // 则将输入字符存储到相应位置(i,j) count++; j++; // 列坐标增加 if(j>c) j=j%c; // 列坐标防止超出范围 } else if(in=='\n' && count>0) i++; // 如果接收到了换行符，则行坐标增加，为防止输入流中多余换行符的干扰，加一个count判断 } //------------------输入网格内部数据完毕 //------------------开始统计并记录起始格 for(i=1; i<=r; i++){ for(j=1; j<=c; j++) // 如果一个白格左边或上边相邻位置没有白格（是黑格或出了边界），那么这是一个起始格 if(a[i][j]!='*' && (a[i-1][j]==0 || a[i-1][j]=='*' || a[i][j-1]==0 || a[i][j-1]=='*')) { heads++; // 起始格数量加1 x[heads] = i; // 记录起始格坐标 y[heads] = j; } } //-----------------起始格统计记录完毕 //-----------------开始输出横向单词 printf("Across\n"); for(i=1;i<=heads;i++) { if(a[x[i]][y[i]-1]==0 || a[x[i]][y[i]-1]=='*'){ // 如果这是一个向右的起始格，则输出横向单词 j = y[i]; printf("=.", i); while(a[x[i]][j]!='*' && a[x[i]][j]!=0) printf("%c", a[x[i]][j++]); printf("\n"); } } //-----------------横向单词输出完毕 //-----------------开始输出纵向单词 printf("Down\n"); for(i=1;i<=heads;i++) { if(a[x[i]-1][y[i]]==0 || a[x[i]-1][y[i]]=='*'){ // 如果这是一个向下的起始格，则输出横向单词 j = x[i]; printf("=.", i); while(a[j][y[i]]!='*' && a[j][y[i]]!=0) printf("%c", a[j++][y[i]]); printf("\n"); } } //-----------------纵向单词输出完毕 scanf("%d", &r); // 读入下一个网格的r，或结束标记0 } return 0; }