UVa512
Spreadsheet Tracking
给定一个表格，和一些操作序列，输出给定单元格在这些操作后的位置。
如果在整个表格上模拟操作，那么就需要记录原始表格和最终表格中每一个单元格的对应关系，比如可以通过给单元格内容编号，新加入的单元格编号全0，删除原始单元格则编号全部改-1，最后在整个表格中搜索原始编号来判断该单元格的最终状态。
但是上述操作太麻烦。记得之前看过一个博客，说如何做一个文本编辑器。看似简单的程序其实特别复杂，主要是插入和删除操作特别难做。用数组就会导致大量的数据移动，但是用链表又特别不值，所以需要有一些折中的做法。
但是对于这道题，只是计算末尾位置，并不要求输出表格内容，所以可以对每一个输入都模拟一遍操作。
#include <iostream> #include <vector> #include <string> #define DR 0 #define DC 1 #define IR 2 #define IC 3 #define EX 4 using namespace std; void delRow(const vector<int> &viOps, int &r) { int del = 0; for (size_t i = 1; i < viOps.size(); i++) { if (viOps[i] < r) del++; else if (viOps[i] == r){ r = 0; return; } } r -= del; } void delCol(const vector<int> &viOps, int &c) { int del = 0; for (size_t i = 1; i < viOps.size(); i++) { if (viOps[i] < c) del++; else if (viOps[i] == c){ c = 0; return; } } c -= del; } void addRow(const vector<int> &viOps, int &r) { int add = 0; for (size_t i = 1; i < viOps.size(); i++) { if (viOps[i] <= r) add++; } r += add; } void addCol(const vector<int> &viOps, int &c) { int add = 0; for (size_t i = 1; i < viOps.size(); i++) { if (viOps[i] <= c) add++; } c += add; } void exchg(const vector<int> &viOps, int &r, int &c) { if (viOps[1] == r && viOps[2] == c){ r = viOps[3]; c = viOps[4]; } else if (viOps[3] == r && viOps[4] == c){ r = viOps[1]; c = viOps[2]; } } void track(const int cnt, const int row, const int col, const vector<vector<int>> &vviOps) { cout << "Spreadsheet #" << cnt << endl; int r, c, track = 0; cin >> track; for (int i = 0; i < track; i++) { cin >> r >> c; cout << "Cell data in (" << r << ',' << c << ") "; for (auto iter = vviOps.begin(); iter != vviOps.end(); iter++) { const vector<int> &viOps = *iter; switch (viOps[0]) { case DR: delRow(viOps, r); break; case DC: delCol(viOps, c); break; case IR: addRow(viOps, r); break; case IC: addCol(viOps, c); break; case EX: exchg(viOps, r, c); break; } if (r == 0 || c == 0) break; } if (r == 0 || c == 0){ cout << "GONE" << endl; } else{ cout << "moved to (" << r << ',' << c << ')' << endl; } } } int main() { int r = 0, c = 0, op = 0, cnt = 0; while (cin >> r >> c){ if (r == 0 && c == 0) break; if (cnt != 0) cout << endl; cin >> op; vector<vector<int>> vviOps(op, vector<int>()); string strOp; int num = 0, r1, c1, r2, c2; for (int i = 0; i < op; i++) { cin >> strOp; if (strOp == "EX"){ vviOps[i].push_back(EX); cin >> r1 >> c1 >> r2 >> c2; vviOps[i].push_back(r1); vviOps[i].push_back(c1); vviOps[i].push_back(r2); vviOps[i].push_back(c2); } else if (strOp[1] == 'R'){ if (strOp[0] == 'D') vviOps[i].push_back(DR); else vviOps[i].push_back(IR); cin >> num; for (int j = 0; j < num; j++) { cin >> r1; vviOps[i].push_back(r1); } } else if (strOp[1] == 'C'){ if (strOp[0] == 'D') vviOps[i].push_back(DC); else vviOps[i].push_back(IC); cin >> num; for (int j = 0; j < num; j++) { cin >> c1; vviOps[i].push_back(c1); } } } track(++cnt, r, c, vviOps); } return 0; } /* 7 9 5 DR 2 1 5 DC 4 3 6 7 9 IC 1 3 IR 2 2 4 EX 1 2 6 5 4 4 8 5 5 7 8 6 5 0 0 */