UVa 285 Crosswords

题目分析本题要求判断给定的填字游戏Crossword \texttt{Crossword}Crossword答案是否正确。填字游戏在一个矩形网格中进行单词可以横向或纵向放置且交叉位置共享同一个字母。题目输入包含两部分单词放置信息若干行每行格式为word x y d表示单词word从坐标(x, y)开始沿着方向d放置。方向d可以是r向右x 增加l向左x 减少d向下y 增加u向上y 减少坐标系统原点在左上角(1, 1)为左上角。输入以一行单独的#表示单词放置信息的结束。答案信息在#之后第一行是填字游戏的最小宽度最右边的列坐标第二行是最小高度最下边的行坐标第三行是从左到右、从上到下排列的所有字母末尾以$符号作为结束标记。题目保证输入的单词放置信息本身是“正确”的不会出现冲突我们需要根据这些单词的放置位置计算出实际占据的网格宽度和高度然后与答案中给出的宽度和高度进行比较同时将网格中的字母按行优先顺序拼接成字符串与答案中的字母序列进行比较。若两者均一致则输出The solution is correct.否则输出The solution is incorrect.。解题思路核心步骤解题代码的整体思路非常清晰可以分为以下几个步骤解析单词放置信息构建填字网格读取答案信息比较实际网格尺寸与答案给出的尺寸比较实际网格中的字母序列与答案给出的字母序列详细分析第一步解析单词放置信息由于输入中单词的起始坐标(x, y)中x和y均为正整数且单词长度小于10 1010坐标范围小于100 100100因此我们可以用一个二维字符数组grid来表示整个填字网格大小设为150 × 150 150 \times 150150×150足矣。对于每一行单词信息我们需要解析出单词word、起始横坐标x、起始纵坐标y和方向d根据方向d确定每一步的偏移量(offsetx, offsety)r(1, 0)l(-1, 0)d(0, 1)u(0, -1)从起始位置开始将单词的每个字母依次填入grid的对应位置同时记录整个网格的最右边列坐标和最下边行坐标即实际宽度和高度这里需要注意坐标(x, y)中x表示列y表示行。题目中minimal width和minimal height的定义分别是“最右边边缘坐标”和“最下边边缘坐标”因此我们在记录时取所有单词起始坐标和结束坐标中的最大值即可。第二步读取答案信息在遇到#后接着读入三行第一行宽度width第二行高度height第三行以$结尾的字母序列其中可能包含空格如样例中的second la nvis e ft 1 e $需要去除空格后得到纯字母字符串第三步比较尺寸将第一步中计算得到的right_most实际宽度和bottom_most实际高度与答案中的width和height进行比较。若不一致则直接判定答案错误。第四步比较字母序列若尺寸一致则需要比较字母序列。按照“从左到右、从上到下”的顺序遍历整个网格行优先将grid中非空格的字符依次取出组成一个字符串text然后与答案中处理得到的纯字母字符串answer进行比较。若相等则正确否则错误。这里有一个细节网格中有些位置可能没有被任何单词覆盖这些位置在初始化时被填充为空格遍历时需要跳过。复杂度分析单词数量未知但每个单词长度小于10 1010坐标范围小于100 100100因此网格规模有限。构建网格的时间复杂度为O ( O(O(单词总数× \times×单词长度) ))网格遍历的时间复杂度为O ( O(O(宽度× \times×高度) ))均在可接受范围内。代码实现// Crosswords// UVa ID: 285// Verdict: Accepted// Submission Date: 2016-06-07// UVa Run Time: 0.020s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;chargrid[150][150],solution[150][150];intright_most,bottom_most;// 处理一行单词放置信息将单词填入 grid并更新实际宽度和高度voidprocess(string line){string word,x,y,d;istringstreamiss(line);isswordxyd;// 根据方向确定步长偏移量intoffsetx,offsety;if(dl)offsetx-1,offsety0;elseif(dr)offsetx1,offsety0;elseif(du)offsetx0,offsety-1;elseif(dd)offsetx0,offsety1;// 将字符串转换为整数坐标注意 x 是列y 是行intistoi(y),jstoi(x),lastii,lastjj;for(intk0;kword.length();k){grid[i][j]word[k];// 填入字母lastii,lastjj;// 记录最后一个位置ioffsety,joffsetx;// 移动}// 更新实际宽度最右边列坐标和实际高度最下边行坐标right_mostmax(right_most,max(stoi(x),lastj));bottom_mostmax(bottom_most,max(stoi(y),lasti));}intmain(intargc,char*argv[]){string line;while(getline(cin,line)){// 初始化right_most0,bottom_most0;memset(grid, ,sizeof(grid));// 处理第一行单词信息process(line);// 继续处理直到遇到 #while(getline(cin,line),line[0]!#)process(line);// 读入答案中的宽度和高度intwidth(getline(cin,line),stoi(line));intheight(getline(cin,line),stoi(line));// 读入答案中的字母序列包含空格以 $ 结尾memset(solution, ,sizeof(solution));getline(cin,line);// 从答案行中提取纯字母序列忽略空格遇到 $ 停止string answer;for(inti0;iline.length();i){if(line[i]$)break;if(!isblank(line[i]))answerline[i];}boolcorrecttrue;// 比较尺寸是否一致if(width!right_most||height!bottom_most)correctfalse;else{// 按行优先顺序从 grid 中提取所有非空格字符string text;for(inti1;iheight;i)for(intj1;jwidth;j)if(!isblank(grid[i][j]))textgrid[i][j];// 比较字母序列correct(answertext);}// 输出结果if(correct)coutThe solution is correct.endl;elsecoutThe solution is incorrect.endl;}return0;}总结本题的核心在于正确解析输入、构建网格并提取字母序列进行比对。解题代码采用直接模拟的方法先根据单词放置信息填充网格并记录边界再与答案信息进行比较。由于数据规模较小这种方法简单且高效。需要注意坐标系的定义以及$符号作为结束标记的处理。