例题4-5 追踪电子表格中的单元格（Spreadsheet Tracking，ACM/ICPC World Finals 1997，UVa512)

本文主要是介绍例题4-5 追踪电子表格中的单元格（Spreadsheet Tracking，ACM/ICPC World Finals 1997，UVa512)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：https://vjudge.net/problem/UVA-512
分类：函数
备注：复杂模拟
前言：理论上这应该是个水题…，但是需要足够的仔细，仔细再仔细！

第一种思路，单点模拟，先说明这确实和作者的原代码没什么差别，我自己的是第二个…
代码如下：

#include<stdio.h>
#include<string.h>
const int maxd = 10000;
int r, c, n, q, r0, c0, kase;
struct Command
{char c[10];int r1, c1, r2, c2;int num, x[20];
}cmd[maxd];
int simulate(int* r0,int* c0)
{for (int i = 0; i < n; i++){if (cmd[i].c[0] == 'E'){if (cmd[i].r1 == *r0 && cmd[i].c1 == *c0) { *r0 = cmd[i].r2; *c0 = cmd[i].c2; }else if (cmd[i].r2 == *r0 && cmd[i].c2 == *c0) { *r0 = cmd[i].r1; *c0 = cmd[i].c1; }}else{int dr = 0, dc = 0;for (int j = 0; j < cmd[i].num; j++){if (cmd[i].c[0] == 'I'){if (cmd[i].c[1] == 'R' && cmd[i].x[j] <= *r0)dr++;if (cmd[i].c[1] == 'C' && cmd[i].x[j] <= *c0)dc++;}else{if (cmd[i].c[1] == 'R' && cmd[i].x[j] == *r0)return 0;if (cmd[i].c[1] == 'C' && cmd[i].x[j] == *c0)return 0;if (cmd[i].c[1] == 'R' && cmd[i].x[j] < *r0)dr--;if (cmd[i].c[1] == 'C' && cmd[i].x[j] < *c0)dc--;}}*r0 += dr; *c0 += dc;}}return 1;
}
int main(void)
{while (scanf("%d%d%d", &r, &c, &n) == 3 && r){for (int i = 0; i < n; i++){scanf("%s", cmd[i].c);if (cmd[i].c[0] == 'E')scanf("%d%d%d%d", &cmd[i].r1, &cmd[i].c1, &cmd[i].r2, &cmd[i].c2);else {scanf("%d", &cmd[i].num);for (int j = 0; j < cmd[i].num; j++)scanf("%d", &cmd[i].x[j]);}}if (kase)printf("\n");printf("Spreadsheet #%d\n", ++kase);scanf("%d", &q);while (q--){scanf("%d%d", &r0, &c0);printf("Cell data in (%d,%d) ", r0, c0);if (simulate(&r0, &c0))printf("moved to (%d,%d)\n", r0, c0);else printf("GONE\n");}}return 0;
}

另一种思路全局模拟：

#include<stdio.h>
#include<stdlib.h>
const int base = 10000;
int r, c, n, q, kase, a[100][100], x[100];
int cmp(const void* a, const void* b)
{return *(int*)a - *(int*)b;
}
void ins(char type, int dis, int x)
{if (type == 'R'){r++;for (int i = r; i >= x + dis + 1; i--)for (int j = 1; j <= c; j++)a[i][j] = a[i - 1][j];for (int j = 1; j <= c; j++)a[x + dis][j] = 0;}else{c++;for (int j = c; j >= x + dis + 1; j--)for (int i = 1; i <= r; i++)a[i][j] = a[i][j - 1];for (int i = 1; i <= r; i++)a[i][x + dis] = 0;}
}
void del(char type, int dis, int x)
{if (type == 'R'){for (int i = x - dis; i < r; i++)for (int j = 1; j <= c; j++)a[i][j] = a[i + 1][j];r--;}else{for (int j = x - dis; j < c; j++)for (int i = 1; i <= r; i++)a[i][j] = a[i][j + 1];c--;}
}
void change()
{char cmd[15];scanf("%s", cmd);if (cmd[0] == 'E'){int x1, y1, x2, y2, tmp;scanf("%d%d%d%d", &x1, &y1, &x2, &y2);tmp = a[x1][y1], a[x1][y1] = a[x2][y2], a[x2][y2] = tmp;}else{int cnt, tmp;scanf("%d", &cnt);for (int i = 0; i < cnt; i++)scanf("%d", &x[i]);qsort(x, cnt, sizeof(int), cmp);if (cmd[0] == 'I')for (int i = 0; i < cnt; i++)ins(cmd[1], i, x[i]);else for (int i = 0; i < cnt; i++)del(cmd[1], i, x[i]);}
}
void find()
{int x, y;scanf("%d%d", &x, &y);for (int i = 1; i <= r; i++)for (int j = 1; j <= c; j++)if (a[i][j] == x * base + y){printf("Cell data in (%d,%d) moved to (%d,%d)\n", x, y, i, j);return;}printf("Cell data in (%d,%d) GONE\n", x, y);
}
int main(void)
{while (scanf("%d%d", &r, &c) == 2 && r){if (kase)printf("\n");printf("Spreadsheet #%d\n", ++kase);for (int i = 1; i <= r; i++)for (int j = 1; j <= c; j++)a[i][j] = i * base + j;scanf("%d", &n);while (n--)change();scanf("%d", &q);while (q--)find();}return 0;
}