题目描述
假设有一个 n×m 的网格。左上角的格子坐标是(1,1),右下角的格子坐
标是(n,m)。网格中有 k 个堵塞的格子,其他的格子是空的。你在空格子(x s ,
y s )的中心向一个对角线方向(也就是东北,西北,东南,西南)发射一束激
光。如果光束碰到堵塞的格子或网格边界,它会反射。在不同情况下光束的反
射方式如下图所示。
过了一会儿,光束进入了一个无限的循环。计算至少被光束通过一次的空
格子数。我们认为光束通过了一个格子的中心才算是通过了这个格子。
输入格式
第一行三个整数 n、m、k,接下来 k 行每行两个整数 x i 和 y i ,表示第 i 个
堵塞的格子的坐标。
最后一行两个整数 x s ,y s 和一个字符串表示激光发出的方向。“NE”,
“NW”,“SE”,“SW”分别表示方向(-1,1),(-1,-1),(1,1),
(1,-1)。
保证输入的堵塞的格子坐标不重复。
输出格式
一行输出光束至少通过一次的空格子数。
样例
样例输入
7 5 3
3 3
4 3
5 3
2 1 SE
样例输出
14
数据范围与提示
30%的数据，$n,m \leqslant 30$。
60%的数据，$n,m \leqslant 1000$。
另20%的数据，$k=0$。
100%的数据，$n,m,k \leqslant 100,000$
题解
30%算法：
我觉得这是这道题的难点所在，因为我到现在还想不出来30%的算法怎么打。
60%算法：
想一想，一共有$n^2$个格子，$4$个方向，那么就有$4 \times n^2$个状态，暴力进去搜就好了。
不过需要注意以下几点：
1.只有当当前状态被访问过了才可以跳出，并不是当前格子被访问过了。
2.如果当前状态没有被访问过，但是当前各自被访问过了，答案不变。
时间复杂度：$O(4\times n^2)$。
期望得分：60分。
另20%算法：
考虑$k=0$，意思就是说，中间没有任何堵塞的格子，那么分为一下三种情况：
1.如果$n \neq m$，那么不管从那个点往哪个方向出发，都一定把整张图全跑一遍，答案即为$n \times m$，记得开$long long$就好了。
2.如果$n=m$，光线沿对角线发射，那么它会射到对角，再反弹回来，答案即为$n$。
3.还是$n=m$，但是光线不沿对角线发射，那么它会转一圈，答案即为$2 \times n$。
期望多得分数：10分。
100%算法：
原文：https://www.cnblogs.com/wzc521/p/11228176.html