UVa 232 Crossword Answers

题目分析

本题是一个填字游戏（Crossword Puzzle\texttt{Crossword Puzzle}Crossword Puzzle）的题目。给定一个r×cr \times cr×c的网格，其中白色格子包含字母，黑色格子用*\texttt{*}*表示。需要按照规则对白色格子进行编号，并分别输出Across（横向）和Down（纵向）的单词列表。

编号规则

一个白色格子是eligible（可编号）的条件为：

1. 该格子位于第一行（i=0i = 0i=0）；
2. 或者该格子位于第一列（j=0j = 0j=0）；
3. 或者该格子左边的格子（同一行，前一列）是黑色格子（*\texttt{*}*）；
4. 或者该格子上边的格子（同一列，前一行）是黑色格子（*\texttt{*}*）。

所有符合条件的格子按行优先顺序依次编号，从111开始。

单词定义规则

• Across单词：从一个编号格开始，向右连续取字母，直到遇到黑色格子或行末结束。
• Down单词：从一个编号格开始，向下连续取字母，直到遇到黑色格子或列末结束。

解题思路

1. 读入数据：读入网格的行数rrr和列数ccc，当r=0r = 0r=0且c=0c = 0c=0时结束输入。

2. 编号阶段：

   • 遍历整个网格，对每个白色格子判断是否符合编号条件。
   • 使用一个二维数组indexer\texttt{indexer}indexer记录每个白色格子的编号（初始为000）。
   • 使用另一个二维数组backup\texttt{backup}backup备份编号，用于输出Down单词时使用（因为输出Across时会修改indexer\texttt{indexer}indexer的值）。

3. 输出Across单词：

   • 按行优先顺序遍历网格。
   • 如果当前格子有编号（indexer[i][j]≠0\texttt{indexer}[i][j] \neq 0indexer[i][j]=0），则：
     • 输出编号（右对齐，宽度为333）；
     • 从当前位置开始向右输出连续的字母，直到遇到*\texttt{*}*或行末；
     • 同时将已输出的格子对应的indexer\texttt{indexer}indexer置为000，避免重复输出。

4. 输出Down单词：

   • 按行优先顺序遍历网格。
   • 如果当前格子有备份编号（backup[i][j]≠0\texttt{backup}[i][j] \neq 0backup[i][j]=0），则：
     • 输出编号（右对齐，宽度为333）；
     • 从当前位置开始向下输出连续的字母，直到遇到*\texttt{*}*或列末；
     • 同时将已输出的格子对应的backup\texttt{backup}backup置为000。

5. 格式要求：

   • 每个测试用例输出前先打印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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;charboard[10][10];// 存储网格，最多10x10intindexer[10][10];// 存储每个白色格子的编号（输出Across时使用）intbackup[10][10];// 备份编号（输出Down时使用）intmain(){cin.tie(0);cout.sync_with_stdio(false);intr,c,cases=0;// r行数，c列数，cases记录当前是第几个测试用例// 当r和c均为0时结束输入while(cin>>r>>c,r&&c){// 读入网格数据for(inti=0;i<r;i++){for(intj=0;j<c;j++){cin>>board[i][j];indexer[i][j]=0;// 初始化编号为0backup[i][j]=0;// 初始化备份为0}}// 第一遍遍历：为符合条件的白色格子编号intcounter=1;for(inti=0;i<r;i++){for(intj=0;j<c;j++){// 只处理白色格子（非'*'）if(board[i][j]!='*'){// 判断是否为eligible格子：// 1. 位于第一行（i == 0）// 2. 位于第一列（j == 0）// 3. 左边格子是黑色（board[i][j-1] == '*'）// 4. 上边格子是黑色（board[i-1][j] == '*'）if(i==0||j==0||(board[i-1][j]=='*')||(j>0&&board[i][j-1]=='*')){indexer[i][j]=counter++;// 分配编号backup[i][j]=indexer[i][j];// 备份编号}}}}// 如果不是第一个测试用例，输出空行分隔if(cases++)cout<<"\n";// 输出测试用例标题cout<<"puzzle #"<<cases<<":"<<"\n";// 输出Across单词cout<<"Across"<<endl;for(inti=0;i<r;i++)for(intj=0;j<c;j++)if(indexer[i][j])// 如果当前格子有编号{// 输出编号，宽度为3，右对齐cout<<setw(3)<<right<<indexer[i][j]<<".";// 向右输出连续的字母for(intk=j;k<c&&board[i][k]!='*';k++){cout<<board[i][k];indexer[i][k]=0;// 标记已输出，避免重复}cout<<"\n";}// 输出Down单词cout<<"Down"<<"\n";for(inti=0;i<r;i++)for(intj=0;j<c;j++)if(backup[i][j])// 如果当前格子有备份编号{// 输出编号，宽度为3，右对齐cout<<setw(3)<<right<<backup[i][j]<<".";// 向下输出连续的字母for(intk=i;k<r&&board[k][j]!='*';k++){cout<<board[k][j];backup[k][j]=0;// 标记已输出，避免重复}cout<<"\n";}}return0;}