问题描述
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 题的前一道习题。有利于熟悉如何对二维数据的输入输出格式进行处理,方便在本题进行调试。
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; } |
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("") |