UVa 232 Crossword Answers（枚举+输入输出）

原题地址

https://vjudge.net/problem/UVA-232

题意：输入r行c列的网格，黑格用 ‘*’ 表示， 每个白格上都填有一个字母。如果一个白格的左邻或上邻位置没有白格（黑格或越界），则称该白格是一个起始格。 首先将所有起始格按照从上到下，从左到右的顺序编号1，2，3…… 接下来找出所有的横向单词（从一个无左邻的起始格开始，向右延伸至黑格或边界），再找出所有的纵向单词（从一个无上邻的起始格开始，向下延伸至白格或边界）。按要求输出这些单词。

解题思路

本题是《算法竞赛入门经典》的习题3-6，是比较基本的枚举题目。

遍历每个格子，首先判断是否满足起始格的要求，如果满足再将以其为开端的横向单词、纵向单词（分别无左邻、上邻）的位置存到across、down结构体数组中。最后控制输出格式。

值得注意的点：

依然和输入字符相关，由于scanf依次读入了row、col值，所以读完col后会多出来一个换行，必须用getchar()吞掉这个回车，不然会被当成数组元素读入。如果题目要求两个连续输入的输出之间有一个空行（Separate output for successive input puzzles by a blank line.）那么不要每个测试之后都多输出一个换行，而是在第一个以后的测试结果输出前打入一个空行，这样可以保证结束标志0后没有换行。结构体里存的是这个单词的起始坐标（二元）和终止坐标（一元，要么横着，要么竖着），直接vector存string也是可以的。小心输出格式，一位编号前输出2个空格，两位编号前输出1个空格。

AC代码

#include <iostream> #include <stdio.h> using namespace std; typedef struct word { int num, si, sj, e; //标号、行号、列号、终止位置后一格 }WORD; char puzzle[15][15]; WORD across[1000], down[1000]; int a,b; bool isEligible(int i, int j) //判断是否合法的开始元 { if (puzzle[i][j] == '*') return false; else if (!i || !j || puzzle[i-1][j] == '*' || puzzle[i][j-1] == '*') return true; return false; } /* void printPuzzle(int r, int c) //检查读入 { for (int i = 0; i < r; ++i) { for (int j = 0; j < c; ++j) printf("%c ", puzzle[i][j]); printf("\n"); } }*/ int main() { int row, col, kase = 0; while (~scanf("%d", &row) && row) //终止条件为row=0 { scanf("%d", &col); getchar(); //吞掉col之后的回车，防止被读为数组元素 kase++; for (int i = 0; i < row; ++i) { for (int j = 0; j < col; ++j) scanf("%c", &puzzle[i][j]); getchar(); //逐个读字符后记得吞掉回车 } //printPuzzle(row, col); //检查读入 a = b = 0; int begin_num = 0; for (int i = 0; i < row; ++i) { for (int j = 0; j < col; ++j) { if (isEligible(i, j)) //是开始元 { begin_num++; //标号+1 int k; if (!j || puzzle[i][j-1] == '*') //可以作为横向开始元素 { k = j+1; //检查其右 while (k < col && puzzle[i][k] != '*') k++; //存入across结构体数组 across[a].num = begin_num; across[a].si = i, across[a].sj = j; across[a].e = k; //结束位置后一个 a++; } if (!i || puzzle[i-1][j] == '*') //可以作为纵向开始元素 { k = i+1; //检查其下 while (k < row && puzzle[k][j] != '*') k++; //存入across结构体数组 down[b].num = begin_num; down[b].si = i, down[b].sj = j; down[b].e = k; //结束位置后一个 b++; } }//标记元素处理结束 }//遍历行内结束 }//遍历每一行结束 if(kase > 1) printf("\n"); //分隔puzzle的输出 printf("puzzle #%d:\n", kase); int i,j,r,c,ending; //输出以across的每个字符开始的横向词 printf("Across\n"); for (i = 0; i<a; ++i) { if (across[i].num < 10) //控制空格 printf(" "); else if (across[i].num < 100) printf(" "); printf("%d.", across[i].num); r = across[i].si; //固定行 ending = across[i].e; for (j = across[i].sj; j < ending; ++j) putchar(puzzle[r][j]); printf("\n"); } //输出以down的每个字符开始的纵向词 printf("Down\n"); for (i = 0; i<b; ++i) { if (down[i].num < 10) //控制空格 printf(" "); else if (down[i].num < 100) printf(" "); printf("%d.", down[i].num); c = down[i].sj; //固定列 ending = down[i].e; for (j = down[i].si; j < ending; ++j) putchar(puzzle[j][c]); printf("\n"); } } return 0; }