在很久以前的黄金时代,澳大利亚的土地是矩形的,它可以被划分成
实现细节
你需要包含头文件 rainbow.h。
你需要实现函数 init 和 colours:
init(R, C, sr, sc, M, S) --- 该函数会在开始时调用并且只会调用一次
- R 和 C: 表示网格的行数和列数
- sr 和 sc: 彩虹蛇的起点坐标
- M: 彩虹蛇移动的步数
- S: 一个长度为 M 的字符串, S[i] 是N、S、E、W之一, 分别表示彩虹蛇的第
次移动是向正北、正南、正东、正西移动一格, 。保证彩虹蛇不会移动到网格外面。
colours(ar, ac, br, bc) --- 在调用init一次之后, 该函数会被总共调用
次 表示你所购买矩形的西北角的格子的坐标, 表示你所购买矩形的东南角的格子的坐标,返回一个整数表示在这种购买方案下最多能够将土地染上多少种不同的颜色 ,
请参考提供的模板文件以获取更多的细节。
样例测试程序
样例测试程序按照以下格式输入:
- 第1行:四个整数
, , 和 ; - 第2行:两个整数
和 ; - 第3行:一个包含
个字符的字符串 , 每个字符是N、S、E、W之一 (如果 则此行应留空); - 第4行到
行:每行四个整数 , , 和 。
样例和解释
函数调用 | 返回值 | 解释 |
---|---|---|
init(6, 4, 3, 3, 9, "NWESSWEWS") | 提供了网格的大小,彩虹蛇的起点和它的移动路径。 | |
colours(2, 3, 2, 3) | 0 | 只有 |
colours(3, 2, 4, 4) | 2 | 河将矩形区域分成了两部分:一部分包含 |
colours(5, 3, 6, 4) | 1 | 矩形区域内不包含河,所有格点都是联通的,所以你最多染 |
colours(1, 2, 5, 3) | 3 | 河将矩形区域分成了三部分:第一部分包含 |
注:上图中的蓝色格子表示河流
样例输入
6 4 9 4 3 3 NWESSWEWS 2 3 2 3 3 2 4 4 5 3 6 4 1 2 5 3
样例输出
0 2 1 3
子任务
对于全部任务,
子任务 | 分数 | R | C | Q |
---|---|---|---|---|
1 | 11 | | | |
2 | 12 | | | |
3 | 24 | | | |
4 | 27 | | | |
5 | 26 | | | |
在本题的 hack 中,你可以提交与样例交互库相同格式的输入,该输入需要满足
时间限制:
空间限制: