UVA232 纵横字谜的答案 Crossword Answers 题解

· · 题解

前言

非常好的一道模拟题。

美中不足的是这很恶心的输出格式，给我们增加了许多的难度，而且题目给的格式和 pdf 里面的差多了，坑了我好多次。

思路

从最棘手的部分——输出开始讲解。

我们可以给整体输出划 3 个部分。

分别是小数据的编号、输出字符前的序号以及输出的串。

如下图

其中第一、三部分是更具题意输出的，主要是第二部分，它到底在干什么呢？说是序号，它也不连续啊。此时我们返回题面，通过研究（指我找了半个小时才找到的规律）发现一个规律：第三部分的第一个字符满足一下其一，就可以使编号增加。

只需在程序里判断即可。

解决了输出的问题，接下来就是如何找出第三部分了。

其实也很简单，一个不为 * 的字符，满足以上四点中的其一，就可以成为起始格，如果是 Across，那么横向输出，直到字符为 * 或边界，否则就纵向输出，直到字符为 * 或边界。

分析到这里了，想必大家都有思路了，下面就给大家放代码解释。

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    //定义变量

    int n,m,i,j,p=0,cnt,t,a[101][101];//p 为测试样例的编号，a 数组的用处后面会讲 
    char s[101][101];

    while(1)//一直输入 
    {
        //多测不清空，爆零两行泪！！ 
        for(i=1;i<=100;i++)
            for(j=1;j<=100;j++)
                a[i][j] = 0;
        //测试样例编号 +1。 
        p++;
        cin>>n;//输入行。 
        if(n==0)//观察输入，发现末尾输入的 0, 只有一个，那我们先输入 n，判断是否为 0 就可以了。 
            return 0;
        cin>>m;
        if(p>1)//细腻的操作 1：上一次操作的末尾加上换行。 
            puts("");
        getchar();//读掉行末可恶的空格。
        //输入字符二位数组 
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                cin>>s[i][j];
        //第一部分输出。 
        printf("puzzle #%d:\n",p);
        puts("Across");
        //cnt 就是第二部分的序号。 
        cnt = 0;
        for(i=1;i<=n;i++)
        {
            t = 0;//t 是一个输出序号的重要基准。 
            for(j=1;j<=m;j++)
            {
                if(s[i][j]=='*')
                    continue;
                //满足其一即可。 
                if(i==1||s[i-1][j]=='*'||j==1||s[i][j-1]=='*')
                {
                    cnt++;//序号 +1。 
                    //a 数组的妙用：存放起始格的位置，这样纵向输出就不用重新统计了。 
                    a[i][j] = cnt;//标记初始格。 
                    if(j>=t)
                    {
                        printf("%3d.",cnt);
                        int k = j;//不能用 j 查找，不然就会使变量错乱。 
                        while(k<=m&&s[i][k]!='*')//一直查找，直到字符不为 “* ”。 
                        {
                            putchar(s[i][k]);//输出 
                            k++; 
                        }
                        t = k;
                        puts("");   
                    }
                }
            }
        }
        puts("Down");//输出一部分。 
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                if(a[i][j])//如果此时是初始格的位置。 
                {
                    printf("%3d.",a[i][j]);//输出序号。 
                    int k = i;
                    while(k<=n&&s[k][j]!='*')//和横向查找类似 
                    {
                        putchar(s[k][j]);
                        a[k][j] = 0;
                        k++;
                    }
                    puts("");
                }
            }
        }
    }
    return 0;
}