UVa 232 Crossword Answers

题目分析本题是一个填字游戏Crossword Puzzle\texttt{Crossword Puzzle}Crossword Puzzle的题目。给定一个r×cr \times cr×c的网格其中白色格子包含字母黑色格子用*\texttt{*}*表示。需要按照规则对白色格子进行编号并分别输出Across横向和Down纵向的单词列表。编号规则一个白色格子是eligible可编号的条件为该格子位于第一行i0i 0i0或者该格子位于第一列j0j 0j0或者该格子左边的格子同一行前一列是黑色格子*\texttt{*}*或者该格子上边的格子同一列前一行是黑色格子*\texttt{*}*。所有符合条件的格子按行优先顺序依次编号从111开始。单词定义规则Across单词从一个编号格开始向右连续取字母直到遇到黑色格子或行末结束。Down单词从一个编号格开始向下连续取字母直到遇到黑色格子或列末结束。解题思路读入数据读入网格的行数rrr和列数ccc当r0r 0r0且c0c 0c0时结束输入。编号阶段遍历整个网格对每个白色格子判断是否符合编号条件。使用一个二维数组indexer\texttt{indexer}indexer记录每个白色格子的编号初始为000。使用另一个二维数组backup\texttt{backup}backup备份编号用于输出Down单词时使用因为输出Across时会修改indexer\texttt{indexer}indexer的值。输出Across单词按行优先顺序遍历网格。如果当前格子有编号indexer[i][j]≠0\texttt{indexer}[i][j] \neq 0indexer[i][j]0则输出编号右对齐宽度为333从当前位置开始向右输出连续的字母直到遇到*\texttt{*}*或行末同时将已输出的格子对应的indexer\texttt{indexer}indexer置为000避免重复输出。输出Down单词按行优先顺序遍历网格。如果当前格子有备份编号backup[i][j]≠0\texttt{backup}[i][j] \neq 0backup[i][j]0则输出编号右对齐宽度为333从当前位置开始向下输出连续的字母直到遇到*\texttt{*}*或列末同时将已输出的格子对应的backup\texttt{backup}backup置为000。格式要求每个测试用例输出前先打印puzzle #x:\texttt{puzzle \#x:}puzzle #x:其中xxx从111开始。Across和Down列表分别以Across\texttt{Across}Across和Down\texttt{Down}Down作为标题。相邻两个测试用例的输出之间用空行分隔。代码实现// Crossword Answers// UVa ID: 232// Verdict: Accepted// Submission Date: 2016-05-11// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;charboard[10][10];// 存储网格最多10x10intindexer[10][10];// 存储每个白色格子的编号输出Across时使用intbackup[10][10];// 备份编号输出Down时使用intmain(){cin.tie(0);cout.sync_with_stdio(false);intr,c,cases0;// r行数c列数cases记录当前是第几个测试用例// 当r和c均为0时结束输入while(cinrc,rc){// 读入网格数据for(inti0;ir;i){for(intj0;jc;j){cinboard[i][j];indexer[i][j]0;// 初始化编号为0backup[i][j]0;// 初始化备份为0}}// 第一遍遍历为符合条件的白色格子编号intcounter1;for(inti0;ir;i){for(intj0;jc;j){// 只处理白色格子非*if(board[i][j]!*){// 判断是否为eligible格子// 1. 位于第一行i 0// 2. 位于第一列j 0// 3. 左边格子是黑色board[i][j-1] *// 4. 上边格子是黑色board[i-1][j] *if(i0||j0||(board[i-1][j]*)||(j0board[i][j-1]*)){indexer[i][j]counter;// 分配编号backup[i][j]indexer[i][j];// 备份编号}}}}// 如果不是第一个测试用例输出空行分隔if(cases)cout\n;// 输出测试用例标题coutpuzzle #cases:\n;// 输出Across单词coutAcrossendl;for(inti0;ir;i)for(intj0;jc;j)if(indexer[i][j])// 如果当前格子有编号{// 输出编号宽度为3右对齐coutsetw(3)rightindexer[i][j].;// 向右输出连续的字母for(intkj;kcboard[i][k]!*;k){coutboard[i][k];indexer[i][k]0;// 标记已输出避免重复}cout\n;}// 输出Down单词coutDown\n;for(inti0;ir;i)for(intj0;jc;j)if(backup[i][j])// 如果当前格子有备份编号{// 输出编号宽度为3右对齐coutsetw(3)rightbackup[i][j].;// 向下输出连续的字母for(intki;krboard[k][j]!*;k){coutboard[k][j];backup[k][j]0;// 标记已输出避免重复}cout\n;}}return0;}