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

UVaOJ 512 - Spreadsheet Tracking

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

问题描述

p512

原题链接:UVaOJ 512 - Spreadsheet Tracking

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

解法一:模拟

模拟题,入门经典上给出的原始解法思路并不推荐,直接根据存下来的指令序列 ops 更新被查询的位置变化就好了。

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
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 警告了:

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
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
AOAPC II UVaOJ 字符串
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz