关键词：
Description
A crossword puzzle consists of a rectangular grid of black and white squares and two lists of definitions (or descriptions).
One list of definitions is for “words” to be written left to right across white squares in the rows and the other list is for words to be written down white squares in the columns. (A word is a sequence of alphabetic characters.)
To solve a crossword puzzle, one writes the words corre- sponding to the definitions on the white squares of the grid.
The definitions correspond to the rectangular grid by
means of sequential integers on “eligible” white squares.
White squares with black squares immediately to the left or
above them are “eligible.” White squares with no squares ei-
ther immediately to the left or above are also “eligible.” No other squares are numbered. All of the squares on the first row are numbered.
The numbering starts with 1 and continues consecutively across white squares of the first row, then across the eligible white squares of the second row, then across the eligible white squares of the third row and so on across all of the rest of the rows of the puzzle. The picture below illustrates a rectangular crossword puzzle grid with appropriate numbering.
An “across” word for a definition is written on a sequence of white squares in a row starting on a numbered square that does not follow another white square in the same row.
The sequence of white squares for that word goes across the row of the numbered square, ending immediately before the next black square in the row or in the rightmost square of the row.
A “down” word for a definition is written on a sequence of white squares in a column starting on a numbered square that does not follow another white square in the same column.
The sequence of white squares for that word goes down the column of the numbered square, ending immediately before the next black square in the column or in the bottom square of the column.
Every white square in a correctly solved puzzle contains a letter.
You must write a program that takes several solved crossword puzzles as input and outputs the lists of across and down words which constitute the solutions.
Input
Each puzzle solution in the input starts with a line containing two integers r and c (1 ≤ r ≤ 10 and 1 ≤ c ≤ 10), where r (the first number) is the number of rows in the puzzle and c (the second number) is the number of columns.
The r rows of input which follow each contain c characters (excluding the end-of-line) which describe the solution. Each of those c characters is an alphabetic character which is part of a word or the character ‘*’, which indicates a black square.
The end of input is indicated by a line consisting of the single number
Output
Output for each puzzle consists of an identifier for the puzzle (puzzle #1:, puzzle #2:, etc.) and the list of across words followed by the list of down words. Words in each list must be output one-per-line in increasing order of the number of their corresponding definitions.
The heading for the list of across words is ‘Across’. The heading for the list of down words is ‘Down’.
In the case where the lists are empty (all squares in the grid are black), the ‘Across’ and ‘Down’ headings should still appear.
Separate output for successive input puzzles by a blank line.
Sample Input
22
AT
*O
67
AIM*DEN
*ME*ONE
UPON*TO
SO*ERIN
*SA*OR*
IES*DEA
0Sample Output
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#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <cctype>
#define MAX 1005
using namespace std;
char s[MAX][MAX]; // 储存网格
int flag[MAX][MAX]; // 记录起始点
char in[5];
int main()
int cnt = 0;
while(~scanf("%[^
]%*c",in) && (in[0]-‘0‘))
memset(flag,0,sizeof(flag)); memset(s,0,sizeof(s)); // 清除内容
int r = in[0]-‘0‘,c = in[2]-‘0‘;
for(int i = 0;i < r;i ++) scanf("%s",s[i]); // 输入网格
int flagCNT = 0;
for(int i = 0;i < r;i ++) // 判断起始点
for(int j = 0;j < c;j ++)
if((s[i][j]!=‘*‘) &&
(i == 0 || j == 0 || s[i-1][j]==‘*‘ || s[i][j-1]==‘*‘))
flag[i][j] = ++flagCNT;
printf("puzzle #%d:
Across
",++cnt);
/*--------------------- 横向输出 --------------------------------*/
bool next = true; bool fis = true;
for(int i = 0;i < r;i ++)
for(int j = 0;j < c;j ++)
if(next && s[i][j]!=‘*‘)
fis ? printf("%4d.",flag[i][j]) :
printf("
%4d.",flag[i][j]);
if(s[i][j]!=‘*‘)
putchar(s[i][j]); next = false;
if(j==c-1 && s[i+1][0]!=‘*‘) next = true;
else fis = false; next = true;
printf("
Down
");
/*--------------------- 纵向输出 --------------------------------*/
next = true; fis = true;
for(int i = 0;i < r;i ++)
for(int j = 0;j < c;j ++)
if(next && s[i][j]!=‘*‘ && flag[i][j] && (i==0 || s[i-1][j]==‘*‘))
fis ? printf("%4d.",flag[i][j]) :
printf("
%4d.",flag[i][j]);
if(flag[i][j] && (i==0 || s[i-1][j]==‘*‘))
int down = i;
while(s[down][j]!=‘*‘ && down < r)
putchar(s[down++][j]); next = false;
fis = false; next = true;
printf("
");
getchar(); // 吞掉输入后的回车
return 0;
《算法竞赛入门经典》之“算法设计与优化策略”
一。构造法UVA120 StacksofFlapjacksTimeLimit: 3000MS 64bitIOFormat: %lld&%lluSubmit Status uDebugDescriptionBackgroundStacksandQueuesareoftenconsideredthebreadandbutt 查看详情
笔记算法竞赛入门经典
contents基础题目选解WERTYU、数据结构基础暴力求解法高效算法设计动态规划初步数学概念与方法图论模型与算法 1、WERTYU刚开始的思路是output[‘S‘]=‘A‘。。。书上的常量表应该会比较通用一点。。而不仅仅适于有序常量。i... 查看详情
随笔笔记算法竞赛入门经典ch3
关于读取scanf()读取到空格自动停止getchar()读取结束返回EOF（整型） 查看详情
算法竞赛入门经典_4.3_递归
...归头，二是递归体。我们使用gcc调试工具H:编程书籍学习算法竞赛入门经典2代码算法入门经典第四章>bf‘b‘不是内部或外部命令，也不是可运行的程 查看详情
随笔笔记算法竞赛入门经典ch4
typedefstruct{doublex,y;}Point;使用typedef可以使结构体使用前不需要加struct 查看详情
算法竞赛入门经典（第2版）+算法艺术与信息学竞赛pdf-高清版免费下载
下载地址：网盘下载备用地址：网盘下载 查看详情
算法竞赛入门经典——训练指南
1.UVa11300我的代码：#include<iostream>#include<cstdio>#include<algorithm>usingnamespacestd;longlongC[1000010],M,a;intmain(){intn;while(~scanf("%d",&n)){C[0]=0;for(inti=1;i<=n;i++){ 查看详情
《算法竞赛入门经典》小收获
1.windows下的命令 6.15 cmd 打开命令窗口dir 文件列表cdmd d 改变创建删除目录cd 返回根目录more ype 显示文件内容fc 比较两个文件内容del ... 查看详情
算法竞赛-入门经典计算并输出1+2的值
1.练习目的:计算并输出1+2的值2.源码:1#include<stdio.h>2intmain()3{45printf("%d ",1+2);6return0;7}3.总结:略... 查看详情
算法竞赛入门经典5.2stl初步(代码片段)
1. 排序和检索，学会使用sort排序，以及low_bound函数RajuandMeenalovetoplaywithMarbles.Theyhavegotalotofmarbleswithnumberswrittenonthem.Atthebeginning,Rajuwouldplacethemarblesoneafteranotherinascendingorderofthenumbersw 查看详情
《算法竞赛入门经典》5.12tex括号
1/*2*在TeX中，左双引号是``，右双引号是‘‘。输入一篇包含双引号的文章，你的任务是把它转换成TeX的格式。3*样例输入："Tobeornottobe,"quoththeBard,"that4*isthequestion".5*样例输出：``Tobeornottobe,‘‘quoththeBard,``that6*isthequestion.7*/8#include&... 查看详情
《算法竞赛入门经典（第2版）》pdf下载在线阅读，求百度网盘云资源
《算法竞赛入门经典（第2版）》（刘汝佳）电子书网盘下载免费在线阅读资源链接：链接：https://pan.baidu.com/s/1hn9oYzCM-fjrw649WmvKyg 提取码：6bov 书名：算法竞赛入门经典（第2版）作者：刘汝佳豆瓣评分：8.9出版社：清... 查看详情
算法竞赛入门经典训练指南pdf高清版免费下载
...载备用地址：网盘下载 基本介绍编辑内容简介《算法竞赛入门经典:训练指南》题目多选自近年来ACM/ICPC区域赛和总决赛真题，内容全面，信息量大，覆盖了常见算法竞赛中的大多数细分知识点。书中还给出了所有重要的... 查看详情
[算法竞赛入门经典]crosswordanswersacm/icpcworldfinals1994,uva232(代码片段)
DescriptionAcrosswordpuzzleconsistsofarectangulargridofblackandwhitesquaresandtwolistsofdefinitions(ordescriptions).Onelistofdefinitionsisfor“words”tobewrittenlefttorightacrosswhitesquaresintherowsand 查看详情
《算法竞赛入门经典》动态规划复习
codevs4979数塔1#defineN1002#include<iostream>3usingnamespacestd;4#include<cstdio>5inta[N][N],b[N][N],n;6intmain()7{8scanf("%d",&n);9for(inti=1;i<=n;++i)10for(intj=1;j<=i;++j)11{12s 查看详情
[算法竞赛入门经典]kickdownacm/icpcneerc2004,uva1587(代码片段)
DescriptionAresearchlaboratoryofaworld-leadingautomobilecompanyhasreceivedanordertocreateaspecialtransmissionmechanism,whichallowsforincrediblyefficientkickdown—anoperationofswitchingtolowergear.After 查看详情
算法竞赛入门经典——读书笔记day1
...类型应一一对应，且每个变量前需要加&符号。1-4：在算法竞赛中，输入前不要打印提示信息。输出完毕后应立即终止程序，不要等待用户按键，因为输入输出过程都是自动的，没有人工干预。1-5：在算法竞赛中不要使用头文... 查看详情
算法竞赛入门经典第2版第1章(代码片段)
...步了解变量的含义 掌握变量交换的三变量法 理解算法竞赛中的程序三部曲：输入、计算、输出 记住算法竞赛的目标及其对程序的要求 &n 查看详情