[Topcoder]SRM369DIV2题解

PirateTreasure

题意：

有8个方向，然后给你一个数组，这个数组描述了朝着那些方向走了多少步。求出发点与终点的距离。

题解：

简单的统计题目，统计x,y的偏移量，最后算出结果。

TurningLightOn

题意：

给你一个棋盘，棋盘上面有0有1，然后翻转一个点为(x，y)的时候，会翻转整个大小为(0..x, 0..y)的矩形。要把所有的棋盘翻转为1，求次数。

题解：

不难看出，只要从右下往左上找到所有的0，枚举翻转即可。

JumpingBoard

题意：

给你一个棋盘，上面有一些数字，还有一些坑，每次能够朝着上下左右移动该位置的数字步，一旦冲出棋盘或者掉坑就会死翘翘。求最多能在棋盘上呆多久。

题解：

我是用搜索解决这个问题的。万物基于搜索。在这个过程中我选择深度优先搜索。思路很简单，就是每次拿到一个数字，就上下左右4个方向搜下去。
既然是个搜索，我们可能需要思考下面几个问题：

• 初始状态： (0, 0)
• 目标状态： 走出地图或者到达一个坑(Hole)，或者陷入一个循环，永远可以不走出地图
• 状态转移：当前位置往上下左右四个方向走下去
• 剪枝：最优解剪枝，用dst[i][j]表示最多花多少步到达dst[i][j]点，如果搜索深度dep小于等于dst，则没必要再搜索下去。

代码：