UVa 512 Spreadsheet Tracking

题目描述题目要求模拟电子表格在行/列的删除、插入和单元格内容交换操作后追踪原始单元格中数据的最终位置。给定初始表格的行数rrr和列数ccc以及一系列操作命令。随后给出若干查询每个查询给出原始表格中的一个单元格坐标(r,c)(r, c)(r,c)需要输出该单元格中的数据最终移动到了哪个位置若数据已被删除则输出GONE。输入格式每个电子表格以一行两个整数rrr和ccc开始r,c≤50r, c \le 50r,c≤50接着一行一个整数nnn操作数。接下来nnn行每行一个操作命令EX r1 c1 r2 c2交换单元格(r1,c1)(r1, c1)(r1,c1)和(r2,c2)(r2, c2)(r2,c2)的内容。DR A x1 x2 ... xA删除行x1,x2,…,xAx1, x2, \ldots, xAx1,x2,…,xA。DC A x1 x2 ... xA删除列x1,x2,…,xAx1, x2, \ldots, xAx1,x2,…,xA。IR A x1 x2 ... xA在行x1,x2,…,xAx1, x2, \ldots, xAx1,x2,…,xA之前各插入一个空行。IC A x1 x2 ... xA在列x1,x2,…,xAx1, x2, \ldots, xAx1,x2,…,xA之前各插入一个空列。操作结束后一行一个整数qqq查询数接下来qqq行每行两个整数r,cr, cr,c表示原始表格中的坐标。输入以r0,c0r0, c0r0,c0结束。输出格式对于每个电子表格输出Spreadsheet #XXXX从111开始。对于每个查询输出Cell data in (r,c) moved to (nr,nc)或Cell data in (r,c) GONE。不同电子表格的输出之间用一个空行分隔。样例输入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输出Spreadsheet #1 Cell data in (4,8) moved to (4,6) Cell data in (5,5) GONE Cell data in (7,8) moved to (7,6) Cell data in (6,5) moved to (1,2)题目分析本题的核心是跟踪每个原始单元格在操作后的位置变化。由于表格最大为50×5050 \times 5050×50可以直接模拟每个单元格的位置。数据结构使用二维数组grid[i][j]\textit{grid}[i][j]grid[i][j]存储原始单元格(i,j)(i, j)(i,j)的当前位置。初始时grid[i][j](i,j)\textit{grid}[i][j] (i, j)grid[i][j](i,j)。操作实现删除行/列对于要删除的行/列将该行/列所有单元格的位置标记为(0,0)(0,0)(0,0)表示GONE。其他行/列根据删除的行/列数量调整位置。插入行/列在指定行/列之前插入新行/列原有行/列的位置向下/向右移动。交换单元格交换两个单元格的位置信息。删除操作的位置调整对于删除操作先将要删除的行/列排序然后对于每个现有的单元格计算其前方有多少被删除的行/列从而得到新位置。也可以直接遍历所有单元格若其行/列在删除列表中则标记为GONE否则新行号 原行号 - 前方删除数量。插入操作的位置调整对于插入操作将要插入的行/列排序然后对于每个单元格新行号 原行号 前方插入数量。复杂度分析每次操作遍历整个表格O(r×c)O(r \times c)O(r×c)r,c≤50r, c \le 50r,c≤50操作数有限完全可接受。代码实现// Spreadsheet Tracking// UVa ID: 512// Verdict: Accepted// Submission Date: 2016-12-23// UVa Run Time: 0.020s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases0;intr,c,n,A,q,originalR,originalC,nextR,nextC;intx[10],z[60];string command;pairint,intgrid[60][60];while(cinrc,r0){for(inti1;ir;i)for(intj1;jc;j)grid[i][j]make_pair(i,j);cinn;for(intk1;kn;k){cincommand;if(commandDR||commandDC||commandIR||commandIC){cinA;for(inti0;iA;i)cinx[i];sort(x,xA);if(commandDR||commandDC){for(inti1;i50;i){if(binary_search(x,xA,i))z[i]i;elsez[i]upper_bound(x,xA,i)-x;}if(commandDR){for(inti1;ir;i)for(intj1;jc;j)if(grid[i][j].first0grid[i][j].second0)grid[i][j].first-z[grid[i][j].first];}else{for(inti1;ir;i)for(intj1;jc;j)if(grid[i][j].first0grid[i][j].second0)grid[i][j].second-z[grid[i][j].second];}}else{for(inti1;i50;i)z[i]upper_bound(x,xA,i)-x;if(commandIR){for(inti1;ir;i)for(intj1;jc;j)if(grid[i][j].first0grid[i][j].second0)grid[i][j].firstz[grid[i][j].first];}else{for(inti1;ir;i)for(intj1;jc;j)if(grid[i][j].first0grid[i][j].second0)grid[i][j].secondz[grid[i][j].second];}}}else{cinoriginalRoriginalCnextRnextC;for(inti1;ir;i)for(intj1;jc;j){if(grid[i][j].firstoriginalRgrid[i][j].secondoriginalC)grid[i][j]make_pair(nextR,nextC);elseif(grid[i][j].firstnextRgrid[i][j].secondnextC)grid[i][j]make_pair(originalR,originalC);}}}if(cases0)cout\n;coutSpreadsheet #cases\n;cinq;for(intk1;kq;k){cinrc;coutCell data in (r,c) ;if(grid[r][c].first0grid[r][c].second0){coutmoved to (;coutgrid[r][c].first,grid[r][c].second)\n;}elsecoutGONE\n;}}return0;}