【UVA – 232】Crossword Answers【紫书】

【UVA – 232】Crossword Answers【紫书】

问题链接:https://vjudge.net/problem/UVA-232

udebug数据链接:https://www.udebug.com/UVa/232

Solution:

解决方案比较简单,读入全部字符后,进行一次搜索,要分开保存每个across的起始和每个down的起始,主要判断是否是起始的方法,就是:

1.为*的位置一定不是起始

2.在不违反1的条件下,在*右边一定是across串的起始,在*的下边一定是down的起始。

3.在满足1的条件下,第一行和第一列的字符一定是起始。

#include <iostream>

using namespace std;

const int LIM = 12;
struct node {
    int r, c, cnt;
};
int cnt;
node across[LIM * LIM], down[LIM * LIM];
int apos, dpos;
char map[LIM][LIM];

inline void clsln() {
    while (getchar() != '\n');
}

int main(void) {
    int r, c;
    for (int k = 1; ~scanf("%d", &r) && r; k++) {
        scanf("%d", &c);
        clsln();
        if (k - 1) putchar('\n');
        printf("puzzle #%d:\n", k);
        // init
        cnt = 1;
        apos = dpos = 0;
        // input
        for (int i = 0; i < r; i++)
            gets(map[i]);
        bool flag = false;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++, flag = false) {
                if (map[i][j] == '*') continue;
                if ((!i && map[i][j] != '*') || (i && map[i - 1][j] == '*')) {
                    down[dpos++] = {i, j, cnt};
                    flag = true;
                }
                if ((!j && map[i][j] != '*') || (j && map[i][j - 1] == '*')) {
                    across[apos++] = {i, j, cnt};
                    flag = true;
                }
                if (flag) cnt++;
            }
        }
        printf("Across\n");
        for (int i = 0; i < apos; i++) {
            printf("%3d.", across[i].cnt);
            int tr = across[i].r;
            for (int tc = across[i].c; tc < c && map[tr][tc] != '*'; tc++)
                putchar(map[tr][tc]);
            putchar('\n');
        }
        printf("Down\n");
        for (int i = 0; i < dpos; i++) {
            printf("%3d.", down[i].cnt);
            int tc = down[i].c;
            for (int tr = down[i].r; tr < r && map[tr][tc] != '*'; tr++)
                putchar(map[tr][tc]);
            putchar('\n');
        }
    }
    return 0;
}