问题描述
p512原题链接：UVaOJ 512 - Spreadsheet Tracking
相关说明：本题为《算法竞赛入门经典（第2版）》例题 4-5
解法一：模拟
模拟题，入门经典上给出的原始解法思路并不推荐，直接根据存下来的指令序列 ops 更新被查询的位置变化就好了。
|
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 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include <bits/stdc++.h> using namespace std; void execute(int &r, int &c, const vector<vector<string>> &ops) { for (auto op : ops) { if (!r || !c) break; string command = op[0]; if (command[0] == 'D') { // "DR" or "DC" int ori_pos = command[1] == 'R' ? r : c; for (int i = 0; i < stoi(op[1]); ++i) { int del = stoi(op[2 + i]); if (del == ori_pos) command[1] == 'R' ? r = 0 : c = 0; if (del < ori_pos) command[1] == 'R' ? r -= 1 : c -= 1; } } else if (command[0] == 'I') { // "IR" or "IC" int ori_pos = command[1] == 'R' ? r : c; for (int i = 0; i < stoi(op[1]); ++i) { int ins = stoi(op[2 + i]); if (ins <= ori_pos) command[1] == 'R' ? r += 1 : c += 1; } } else if (command == "EX") { int r1 = stoi(op[1]), r2 = stoi(op[3]); int c1 = stoi(op[2]), c2 = stoi(op[4]); if (r == r1 && c == c1) r = r2, c = c2; else if (r == r2 && c == c2) r = r1, c = c1; } } return; } int main() { int r, c, num_r, num_c, num_ops, num_querry, num_seq = 0; while (cin >> num_r >> num_c && num_r && num_c) { num_seq > 0 ? cout << endl : cout << ""; cout << "Spreadsheet #" << ++num_seq << endl; cin >> num_ops; getchar(); vector<vector<string>> ops; string line, tmp; while (num_ops--) { vector<string> op; getline(cin, line); istringstream l(line); while (l >> tmp) op.push_back(tmp); ops.push_back(op); } cin >> num_querry; while (num_querry--) { cin >> r >> c; cout << "Cell data in (" << r << "," << c << ") "; execute(r, c, ops); if (r && c) cout << "moved to (" << r << "," << c << ")" << endl; else cout << "GONE" << endl; } } return 0; } |
Python 解法能 AC，只是懒得去处理 Pylint 警告了：
|
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 48 49 50 51 52 53 54 |
def execute(r: int, c: int, ops: list): for op in ops: if not r or not c: break command = op[0] if command[0] == 'D': ori_pos = r if command[1] == 'R' else c for i in range(int(op[1])): delete = int(op[2 + i]) if delete <= ori_pos: if command[1] == 'R': r = 0 if delete == ori_pos else r - 1 else: c = 0 if delete == ori_pos else c - 1 elif command[0] == 'I': ori_pos = r if command[1] == 'R' else c for i in range(int(op[1])): ins = int(op[2 + i]) if ins <= ori_pos: if command[1] == 'R': r = r + 1 else: c = c + 1 elif command == "EX": r1, c1, r2, c2 = map(int, op[1:]) if r == r1 and c == c1: r, c = r2, c2 elif r == r2 and c == c2: r, c = r1, c1 return r, c num_seq = 0 while True: num_r, num_c = map(int, input().split()) if num_r and num_c: print("\n" if num_seq > 0 else "", end="") num_seq += 1 print(f"Spreadsheet #{num_seq}") ops = [] num_ops = int(input()) for i in range(num_ops): ops.append(input().split()) num_querry = int(input()) for i in range(num_querry): r, c = map(int, input().split()) tr, tc = execute(r, c, ops) print(f"Cell data in ({r},{c})", f"moved to ({tr},{tc})" if tr and tc else "GONE") else: break |
