MEGChai MEGChai
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
首页 › 数据结构与算法 › 在线评测 › UVaOJ 232 - Crossword Answers
AOAPC II

UVaOJ 232 - Crossword Answers

Chai
2021-11-24 0:00:00在线评测阅读 276

问题描述

p232

原题链接:UVaOJ 232 - Crossword Answers

相关说明:本题为《算法竞赛入门经典(第2版)》习题 3-6

解法一:模拟

需要细心做的一题,如果觉得不好理解,可以拆成分别考虑 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 题的前一道习题。有利于熟悉如何对二维数据的输入输出格式进行处理,方便在本题进行调试。

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#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;
}
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
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 字符串
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz