银杏林

小 Y 每天上学和放学都会穿过这片银杏林。

银杏林可以看作一片 $n*m$ 的矩形区域，上面有一些银杏树用"T"表示，空地用"."表示。

其中有一些的小路用字符 "R" 表示。

小 Y 很喜欢晒太阳，但树会挡住阳光，阳光无法穿过树。

现在需要回答 $Q$ 个询问，每次都要回答太阳从不同方向照来时小路上有多少处有阳光。

为了方便描述，这里给出一种描述阳光方向的方法：

对于每个询问给出两个整数 $x,y$ 表示阳光的方向，阳光方向即依次经过 $(0,0)$ ， $(x,y)$ 的射线的方向。

与 x 轴正半轴交点坐标为整数或 y 轴正半轴交点坐标为整数的的若干条平行与给定射线的射线都视作阳光（同时经过0,0 也算）。

数据保证： $x * y >= 0$ && $x , y$ 不同时等于 $0$ ！

同时阳光在题目中并不是从给定矩阵的 $(0,0)$ 点出发的，下面给出一个解释

解释:

$x > 0 , y > 0$ 的时候表示阳光从 给定矩形的左下方 射向 给定矩形的右上方

$x < 0 , y < 0$ 的时候表示阳光从 给定矩形的右上方 射向 给定矩形的左下方

当注意矩阵一直是处于第一象限的，矩阵的行（n 那一维代表 y），矩阵上面的 $(x_i,y_i)$ 对应平面直角坐标系上坐标就是 $(n - x_i + 1, y_i)$ 。

例如阳光方向为 : (2, 1)，下面三条蓝色的线都是“阳光”

第一行给定 $n$ ， $m$ 同题面。

第 $2$ ~ $n+1$ 行给定 $n$ 行长为 $m$ 的字符串，其中 $.$ 代表空地， $T$ 代表银杏树， $R$ 代表小路

第 $n+2$ 行给定 $Q$ 表示询问数量。

为了方便描述，这里给出一种描述阳光方向的方法：

对于每个询问给出两个整数 $x,y$ 表示阳光的方向，阳光方向即依次经过 $(0,0)$ ， $(x,y)$ 的射线（方向是 $(0,0)$ 指向 $(x,y)$ ）。

请尽量自行联系描述以及上面的例子理解。

下图中黄色点表示银杏树，绿色点表示小路，橙色线条代表阳光。

#include <stdio.h> #include <string.h> #define N 1005 int n, m, q, i, j, k, x, y, xx, yy, ans, c[N][N]; char s[N]; int cal(int xx, int yy){ int s = 0; while(xx<=m && yy<=n){ if(c[xx][yy] == 1) s++; if(c[xx][yy] < 0){ if(!k) break; else s = 0; } xx += x, yy += y; } return s; } int main(){ scanf("%d%d", &n, &m); for(i=0; i<n; i++){ scanf("%s", s+1); for(j=1; j<=m; j++){ if(s[j] == 'R') c[j][n-i] = 1; if(s[j] == 'T') c[j][n-i] = -1; } } scanf("%d", &q); while(q--){ scanf("%d%d", &x, &y); for(i=0; i<=n; i++) k = ans = 0; if(x < 0 || y < 0) k = 1, x = -x, y = -y; if(!x) y = 1; if(!y) x = 1; for(i=2; i<=x; i++){ while(x%i == 0 && y%i == 0) x /= i, y /= i; }//计算最近点(x, y) for(i=x; i<=m; i++) ans += cal(i, y); for(i=y+1; i<=n; i++) ans += cal(x, i); printf("%d\n", ans); } return 0; }

详情