#include // UVa512 Spreadsheet Tracking (算法1) #define maxd 100 #define BIG 10000 int r, c, n, d[maxd][maxd], d2[maxd][maxd], ans[maxd][maxd], cols[maxd]; //数据结构r c是一开始的行数和列数 void copy(char type, int p, int q) { if (type == 'R') { for (int i = 1; i <= c; i++) d[p][i] = d2[q][i]; } else { for (int i = 1; i <= r; i++) d[i][p] = d2[i][q]; } } void del(char type) { memcpy(d2, d, sizeof(d));//d2中的内容和d中的内容是完全一样的 int cnt = type == 'R' ? r : c, cnt2 = 0; for (int i = 1; i <= cnt; i++) {//如果是要删除行的话,cnt就是行 if (!cols[i]) copy(type, ++cnt2, i);//如果这一row或者col没有被删除,那么就被复制到d2表格中去,copy函数中的i(q)是可以留下来的行,cnt2就是剩下了多少行 } //这一步就相当于依照和d一模一样的d2来重新写d,然后重新更新r 和c 的值,这样就不用将d剩下的部分清0了 if (type == 'R') r = cnt2; else c = cnt2; } void ins(char type) { memcpy(d2, d, sizeof(d)); int cnt = type == 'R' ? r : c, cnt2 = 0; for (int i = 1; i <= cnt; i++) { if (cols[i]) copy(type, ++cnt2, 0);//需要在第i行插入一行,这个想法特别的巧妙 copy(type, ++cnt2, i); } if (type == 'R') r = cnt2; else c = cnt2; } int main() { int r1, c1, r2, c2, q, kase = 0; //命令字符串 char cmd[10]; memset(d, 0, sizeof(d)); //r:行数 c:列数 //n:你的任务是模拟这样的n个操作 //&&r -->如果r为负数则是退出的意思 while (scanf("%d%d%d", &r, &c, &n) == 3 && r) { //按行 for (int i = 1; i <= r; i++) //按列 for (int j = 1; j <= c; j++) /* 当坐标信息(或向量各元素)的取值范围较小时,一个整形其实可以存储多个元 例如:(x,y)其中x<100, y<100,则可直接用一个整形来存储该向量(就像segment一样) int v = x * BIG + y; //其中BIG = 100 ,或者比100更大的10的幂 而提取(x,y)时,(v / BIG, v % BIG)就是其对应向量 黄海总结:其实就是用一个变更,描述一个坐标值,节约空间的一种技巧。 */ d[i][j] = i * BIG + j; //初始化? //一共有n个操作 while (n--) { scanf("%s", cmd); //读入命令 //如果是交换指令 if (cmd[0] == 'E') { scanf("%d%d%d%d", &r1, &c1, &r2, &c2);//交换,两个坐标,4个值 //利用中间值变量法进行交换 int t = d[r1][c1]; d[r1][c1] = d[r2][c2]; d[r2][c2] = t; } else { //不是交换命令,那么就可能是删除或者插入 int a, x; //a代表要插入或者删除多少行,这个时候开始进行插入或者删除操作 scanf("%d", &a); //将临时要用的这个一维的行数组或列数组清零 memset(cols, 0, sizeof(cols)); for (int i = 0; i < a; i++) { scanf("%d", &x); cols[x] = 1; }//col里面保存的是一些需要操作的行或者列 if (cmd[0] == 'D') del(cmd[1]); else ins(cmd[1]);//cmd[1]保存的是行或者列 } } memset(ans, 0, sizeof(ans));//这一步开始写答案 for (int i = 1; i <= r; i++)//依据此时的表格中的内容来得到此时的d[i][j]中存放的是原来的哪一个cell,并记录进ans表格中 for (int j = 1; j <= c; j++) { ans[d[i][j] / BIG][d[i][j] % BIG] = i * BIG + j;//ans中保存的是原来的某个cell,现在在哪个cell中 } if (kase > 0) printf("\n"); printf("Spreadsheet #%d\n", ++kase); scanf("%d", &q); while (q--) { scanf("%d%d", &r1, &c1); printf("Cell data in (%d,%d) ", r1, c1); if (ans[r1][c1] == 0) printf("GONE\n"); else printf("moved to (%d,%d)\n", ans[r1][c1] / BIG, ans[r1][c1] % BIG); } } return 0; }