UVaOJ 232 - Crossword Answers

问题描述

解法一：模拟

需要细心做的一题，如果觉得不好理解，可以拆成分别考虑 Across / Down 方向的两道题。由于 start_number 的分布是有行列规律的，需要遍历 nums 表判断当前块是否能作为起始点。对于 Across 方向的情况，处理起来比较简单，从 j=0 处开始，每次输出字符后位置向右边挪动，使用 * 作为每次输出的终止判断符号即可。如果可以再次合法右挪，将会到达新的起始点，此时其左方位置一定是 * 符号；对于 Down 方向的情况，还需要额外注意：能够作为起始点的位置 (i, j) 其要么位于 i=0 行，要么上方 (i-1, j) 的位置处为 * 符号。

做这题有点吃力的话，可以先做习题 3-5 谜题（Puzzle, ACM/ICPC World Finals 1993, UVa 227），在紫书上 227 题也是 232 题的前一道习题。有利于熟悉如何对二维数据的输入输出格式进行处理，方便在本题进行调试。

#include <bits/stdc++.h>

using namespace std;

int main() {
  int game_cnt = 0, r, c;
  string line;

  while (getline(cin, line) && line != "0") {
    cout << (game_cnt++ ? "\n" : "");
    cout << "puzzle #" << game_cnt << ":" << endl;

    istringstream(line) >> r >> c;
    vector<vector<char>> grid(r, vector<char>(c));
    vector<vector<int>> nums(r, vector<int>(c));
    int start_number = 0;

    for (int i = 0; i < r; ++i) {
      getline(cin, line);
      for (int j = 0; j < c; ++j) {
        grid[i][j] = line[j];
        if (grid[i][j] != '*' && (i == 0 || j == 0 || grid[i - 1][j] == '*' ||
                                  grid[i][j - 1] == '*'))
          nums[i][j] = ++start_number;
      }
    }

    cout << "Across" << endl;
    for (int i = 0; i < r; ++i)
      for (int j = 0; j < c; ++j)
        if (grid[i][j] != '*') {
          cout << right << setw(3) << nums[i][j] << ".";
          while (j < c && grid[i][j] != '*') cout << grid[i][j++];
          cout << endl;
        }

    cout << "Down" << endl;
    for (int i = 0; i < r; ++i)
      for (int j = 0; j < c; ++j)
        if (grid[i][j] != '*' && (!i || grid[i - 1][j] == '*')) {
          cout << right << setw(3) << nums[i][j] << ".";
          for (int p = i; p < r && grid[p][j] != '*'; ++p) cout << grid[p][j];
          cout << endl;
        }
  }
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {

int game_cnt = 0, r, c;

string line;

while (getline(cin, line) && line != "0") {

cout << (game_cnt++ ? "\n" : "");

cout << "puzzle #" << game_cnt << ":" << endl;

istringstream(line) >> r >> c;

vector<vector<char>> grid(r, vector<char>(c));

vector<vector<int>> nums(r, vector<int>(c));

int start_number = 0;

for (int i = 0; i < r; ++i) {

getline(cin, line);

for (int j = 0; j < c; ++j) {

grid[i][j] = line[j];

if (grid[i][j] != '*' && (i == 0 || j == 0 || grid[i - 1][j] == '*' ||

grid[i][j - 1] == '*'))

nums[i][j] = ++start_number;

}

cout << "Across" << endl;

for (int i = 0; i < r; ++i)

for (int j = 0; j < c; ++j)

if (grid[i][j] != '*') {

cout << right << setw(3) << nums[i][j] << ".";

while (j < c && grid[i][j] != '*') cout << grid[i][j++];

cout << endl;

}

cout << "Down" << endl;

for (int i = 0; i < r; ++i)

for (int j = 0; j < c; ++j)

if (grid[i][j] != '*' && (!i || grid[i - 1][j] == '*')) {

cout << right << setw(3) << nums[i][j] << ".";

for (int p = i; p < r && grid[p][j] != '*'; ++p) cout << grid[p][j];

cout << endl;

}

return 0;

}

game_cnt = 0
while True:
    line = input()
    if line == "0":
        break
    game_cnt += 1
    print("{}puzzle #{}:".format("\n" if game_cnt > 1 else "", game_cnt))
    r, c = list(map(int, line.split()))
    grid = [["" for _ in range(c)] for _ in range(r)]
    nums = [[0 for _ in range(c)] for _ in range(r)]

    start_number = 0
    for i in range(r):
        line = input()
        for j in range(c):
            grid[i][j] = line[j]
            if grid[i][j] != "*" and (i == 0 or j == 0 or
                                      grid[i - 1][j] == "*" or grid[i][j - 1] == "*"):
                start_number += 1
                nums[i][j] = start_number

    print("Across")
    for i in range(r):
        j = 0
        while j < c:
            if grid[i][j] != '*':
                print("{nums[i][j]),:>3}.", end="")
                while (j < c and grid[i][j] != "*"):
                    print(grid[i][j], end="")
                    j += 1
                print("")
            j += 1

    print("Down")
    for i in range(r):
        for j in range(c):
            if (grid[i][j] != '*' and (not i or grid[i - 1][j] == "*")):
                print("{nums[i][j]),:>3}.", end="")
                p = i
                while (p < r and grid[p][j] != "*"):
                    print(grid[p][j], end="")
                    p += 1
                print("")

game_cnt = 0

while True:

line = input()

if line == "0":

break

game_cnt += 1

print("{}puzzle #{}:".format("\n" if game_cnt > 1 else "", game_cnt))

r, c = list(map(int, line.split()))

grid = [["" for _ in range(c)] for _ in range(r)]

nums = [[0 for _ in range(c)] for _ in range(r)]

start_number = 0

for i in range(r):

line = input()

for j in range(c):

grid[i][j] = line[j]

if grid[i][j] != "*" and (i == 0 or j == 0 or

grid[i - 1][j] == "*" or grid[i][j - 1] == "*"):

start_number += 1

nums[i][j] = start_number

print("Across")

for i in range(r):

j = 0

while j < c:

if grid[i][j] != '*':

print("{nums[i][j]),:>3}.", end="")

while (j < c and grid[i][j] != "*"):

print(grid[i][j], end="")

j += 1

print("")

j += 1

print("Down")

for i in range(r):

for j in range(c):

if (grid[i][j] != '*' and (not i or grid[i - 1][j] == "*")):

print("{nums[i][j]),:>3}.", end="")

p = i

while (p < r and grid[p][j] != "*"):

print(grid[p][j], end="")

p += 1

print("")

AOAPC II UVaOJ 字符串