Uva - 512 - Spreadsheet Tracking

时间:2022-09-08 19:17:58

Data in spreadsheets are stored in cells, which are organized in rows (r) and columns (c). Some operations on spreadsheets can be applied to single cells (r,c), while others
can be applied to entire rows or columns. Typical cell operations include inserting and deleting rows or columns and exchanging cell contents.

Some spreadsheets allow users to mark collections of rows or columns for deletion, so the entire collection can be deleted at once. Some (unusual) spreadsheets allow users to mark collections of rows or columns for insertions too. Issuing an insertion command
results in new rows or columns being inserted before each of the marked rows or columns. Suppose, for example, the user marks rows 1 and 5 of the spreadsheet on the left for deletion. The spreadsheet then shrinks to the one on the right.

Uva - 512 - Spreadsheet Tracking Uva - 512 - Spreadsheet Tracking

If the user subsequently marks columns 3, 6, 7, and 9 for deletion, the spreadsheet shrinks to this.

Uva - 512 - Spreadsheet Tracking 1 2 3 4 5
1 2 24 8 22 16
2 18 19 21 22 25
3 24 25 67 22 71
4 16 12 10 22 58
5 33 34 36 22 40

If the user marks rows 2, 3 and 5 for insertion, the spreadsheet grows to the one on the left. If the user then marks column 3 for insertion, the spreadsheet grows to the one in the middle. Finally, if the
user exchanges the contents of cell (1,2) and cell (6,5), the spreadsheet looks like the one on the right.

Uva - 512 - Spreadsheet Tracking Uva - 512 - Spreadsheet Tracking Uva - 512 - Spreadsheet Tracking

You must write tracking software that determines the final location of data in spreadsheets that result from row, column, and exchange operations similar to the ones illustrated here.

Input

The input consists of a sequence of spreadsheets, operations on those spreadsheets, and queries about them. Each spreadsheet definition begins with a pair of integers specifying its initial number of rows
(r) and columns (c),
followed by an integer specifying the number (n) of spreadsheet operations. Row and column labeling begins with 1. The maximum number
of rows or columns of each spreadsheet is limited to 50. The following n lines specify the desired operations.

An operation to exchange the contents of cell (r1c1) with the contents of cell (r2,c2) is given by:

EX r1 c1 r2 c2

The four insert and delete commands--DC (delete columns), DR (delete rows), IC (insert columns), and IR (insert rows) are given by:

<commandA x1 x2 Uva - 512 - Spreadsheet Tracking xA

where <command> is one of the four commands; A is a positive integer less than 10, andUva - 512 - Spreadsheet Tracking are the labels of
the columns or rows to be deleted or inserted before. For each insert and delete command, the order of the rows or columns in the command has no significance. Within a single delete or insert command, labels will be unique.

The operations are followed by an integer which is the number of queries for the spreadsheet. Each query consists of positive integers r and c, representing the row and column number of a cell in the original spreadsheet. For each query, your
program must determine the current location of the data that was originally in cell (rc). The end of input is indicated by a row consisting of a pair of zeros for the spreadsheet dimensions.

Output

For each spreadsheet, your program must output its sequence number (starting at 1). For each query, your program must output the original cell location followed by the final location of the data or the
word GONE if the contents of the original cell location were destroyed as a result of the operations. Separate output from different spreadsheets with a blank line.

The data file will not contain a sequence of commands that will cause the spreadsheet to exceed the maximum size.

Sample Input

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

Sample Output

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)

先把命令保存下来,每次询问之后对询问位置执行一次操作,效率也不错。

AC代码:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>

using namespace std;

const int maxd = 10000;

struct Command
{
	char c[5];
	int r1, c1, r2, c2;
	int a, x[20];
} cmd[maxd];
int r, c, n;

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].a; j++) {
				int x = cmd[i].x[j];
				if (cmd[i].c[0] == 'I') {
					if (cmd[i].c[1] == 'R' && x <= r0) {
						dr++;
					}
					if (cmd[i].c[1] == 'C' && x <= c0) {
						dc++;
					}
				}
				else {
					if (cmd[i].c[1] == 'R' && x == r0) {
						return 0;
					}
					if (cmd[i].c[1] == 'C' && x == c0) {
						return 0;
					}
					if (cmd[i].c[1] == 'R' && x < r0) {
						dr--;
					}
					if (cmd[i].c[1] == 'C' && x < c0) {
						dc--;
					}
				}
			}
			r0 += dr;
			c0 += dc;
		}
	}
	return 1;
}

int main()
{
	int r0, c0, q, kase = 0;
	while (scanf("%d%d", &r, &c) == 2 && r) {
		scanf("%d", &n);
		// 把命令记录下来
		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].a);
				for (int j = 0; j < cmd[i].a; j++) {
					scanf("%d", &cmd[i].x[j]);
				}
			}
		}
		if (kase > 0) 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("GONE\n");
			}
			else {
				printf("moved to (%d,%d)\n", r0, c0);
			}
		}
	}

	return 0;
}

Uva - 512 - Spreadsheet Tracking的更多相关文章

  1. Spreadsheet Tracking

     Spreadsheet Tracking  Data in spreadsheets are stored in cells, which are organized in rows (r) and ...

  2. 【例题 4-5 uva 512】Spreadsheet Tracking

    [链接] 我是链接,点我呀:) [题意] 在这里输入题意 [题解] 每个操作对与一个点来说变化是固定的. 因此可以不用对整个数组进行操作. 对于每个询问,遍历所有的操作.对输入的(x,y)进行相应的变 ...

  3. uva 512

    1. 问题 不知道怎么存储操作 看代码注释,else if等 2. 代码 #include <iostream> #include <stdio.h> #include &lt ...

  4. 踪电子表格中的单元格(Spreadsheet Tracking&comma; ACM&sol;ICPC World Finals 1997&comma; UVa512)

    有一个r行c列(1≤r,c≤50)的电子表格,行从上到下编号为1-r,列从左到右编号为1 -c.如图4-2(a)所示,如果先删除第1.5行,然后删除第3, 6, 7, 9列,结果如图4-2(b) 所示 ...

  5. UVA 215 Spreadsheet Calculator (模拟)

    模拟题.每个单元格有表达式就dfs,如果有环那么就不能解析,可能会重复访问到不能解析的单元格,丢set里或者数组判下重复. 这种题首先框架要对,变量名不要取的太乱,细节比较多,知道的库函数越多越容易写 ...

  6. 思维水题:UVa512-Spreadsheet Tracking

    Spreadsheet Tracking Data in spreadsheets are stored in cells, which are organized in rows (r) and c ...

  7. Spreadsheet Calculator 电子表格计算器 &lpar;Uva 215&rpar;

    原题:https://uva.onlinejudge.org/external/2/215.pdf 有一个M x N的表格,每个单元格是个数字或者表达式.表达式由单元格编号和+ - 号组成 输出单元格 ...

  8. Learning a Deep Compact Image Representation for Visual Tracking

    这篇博客对论文进行了部分翻译http://blog.csdn.net/vintage_1/article/details/19546953,不过个人觉得博主有些理解有误. 这篇博客简单分析了代码htt ...

  9. CUDA Samples&colon; Ray Tracking

    以下CUDA sample是分别用C++和CUDA实现的生成光线跟踪图像,并对其中使用到的CUDA函数进行了解说,code参考了<GPU高性能编程CUDA实战>一书的第六章,CUDA各实现 ...

随机推荐

  1. python安装locustio报错error&colon; invalid command &&num;39&semi;bdist&lowbar;wheel&&num;39&semi;的解决方法

    locust--scalable user load testing tool writen in Python(是用python写的.规模化.可扩展的测试性能的工具) 安装locustio需要的环境 ...

  2. lightoj&period;1048&period;Conquering Keokradong&lpar;二分 &plus; 贪心)

    Conquering Keokradong Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%lld & %llu ...

  3. 蓝牙—逻辑链路控制和适配协议&lpar;L2CAP&rpar;

    L2CAP(Logical Link Control and Adaption Protocol),链路控制和适配协议,位于基带层之上,将基带层的数据分组交换以便于高层应用的数据分组格式,并提供复用和 ...

  4. ManualResetEvent的使用与介绍

    它可以通知一个或多个正在等待的线程已发生事件,允许线程通过发信号互相通信,来控制线程是否可心访问资源 当一个线程开始一个活动(此活动必须完成后,其他线程才能开始)时,它调用 Reset 以将 Manu ...

  5. c&plus;&plus;编程思想(四)--对象和隐藏(感觉书上有误)

    c++编程思想里数据抽象和隐藏实现实际就是通常所说的类和封装: 封装,继承,多态对象特点说的很多,就不再说了 关于封装,本人觉得书上有个地方写的有问题,p145和p153都提到Y::f(X*)引用了X ...

  6. SQLserver2008r2安装过程

    首先,下载SQLserver2008的安装包,下载完成打开是以下界面 点击开始安装,随着安装进程,点下一步 . 接着来到设置角色的过程,点击SQL功能安装 然后按下一步,来到功能选择,点击" ...

  7. 二叉树的递归遍历 天平UVa839

    题意:输入一个树状的天平,利用杠杆原理,根据力矩是否相等(W1D1==W1D2)判断天平是否平衡 解题思路:1.由于判断天平是否平衡,当W1和W2都为0的时候,会先输入左子树,再输入右子树 2.此时的 ...

  8. 【转】shell学习笔记(六)——流程控制之for循环

    基本语法格式: for 变量 in 列表 do 命令行(通常用到循环变量) done ********Linux Shell for循环写法总结******** for((i=1;i<</ ...

  9. Confluence 6 创建一个项目空间

    火星移民小组的程序需要一个地方能够调出他们任务的相关关键信息和资源,你的任务就是帮助他们实现和管理这个需求.这部分是比较容易实现的,因为这些信息需要让空间项目组中完全可见. 这样的话,你就可以设置项目 ...

  10. &lbrack;TC11326&rsqb;ImpossibleGame

    [TC11326]ImpossibleGame 题目大意: 一类字符串仅由'A','B','C','D'四种字母组成.对于这样的一个字符串\(S\),可以用以下两种方式之一修改这个字符串: 交换\(S ...