题意：给一个M*N的矩形区域，有M*N个方格，有些方格为空（可到达），有些非空（不可达）。现A和B在博弈，他们任选两个不同的空格，站在各自的格子中央，A可以移动，但只能进行一次行方向或列向方移动，移动后仍然在格子中央。A如果移动到一个位置使得B看不见他，则A获胜。B看不见A的条件是存在一个非空格子与B到A的线段相切或相交。问，，对于每个空格子，A站在上面，是否无论B在哪里，他都可以移动到一个安全位置。
A可以选择不移动，题目保证至少有两个空格子，每次移动只能进行横向或竖向移动，不能都进行。空格子内部全空，非空格子内部和边界非空。M,N 不超过30
链接： J题
解法：由于M,N 不超过30，可以考虑暴力做。假如我们已经知道站在任意两个空格子上能否相互看到，下面就好做了。
一，如何知道站在任意两个空格子上能否相互看到 暴力枚举任意两个空格子，判断他们中心点连线的线段，是否被一个非空格子挡住，这里需要优化，如果暴力枚举每个非空格子，效率比较低，不如枚举以两个空格子为顶点的小矩形的每一列，并且每次只访问非空格子。这里需要预处理一个函数，表示每个格子下面第一个非空格子在哪。
二，知道了后怎么办 知道了后，枚举每个空格子，假设B在它上面，再暴力枚举每个空格子，假设A终点位置在其上面，如果A和B被挡住了，则表示A所在的空格子是安全位置，那么能到达它的位置都是安全的，除了B所在位置以外（因为A和B不可选同一个格子）。记录下对于每个B所在的空格子，每个空格子是否是安全的，最后判断每个空格子安全指数是否是空格子个数减1即可。
小结：说了那么多，这题用到几何的部分，只有线段与线段相交，这里的相交指广义上的，即只要有交点就算相交。判线段相交的函数如下：
struct Seg{Point p1, p2;Seg(){};Seg(Point p11, Point p22){p1 = p11, p2 = p22;}};bool PointOnSeg(Point p, Seg s){if((s.p1 – p) / (s.p2 – p)) return false;else if(sgn((s.p1 – p) * (s.p2 – p)) > 0) return false;else return true;}bool operator / (const Seg a, const Seg b){//此函数容易写错，且不同题目需要修改，特别注意if((a.p2 – a.p1) || (b.p2 – b.p1)){return PointOnSeg(a.p1, b) || PointOnSeg(a.p2, b) ||PointOnSeg(b.p1, a) || PointOnSeg(b.p2, a);}else return sgn((a.p2 – a.p1) % (b.p1 – a.p1)) * sgn((a.p2 – a.p1) % (b.p2 – a.p1)) <= 0 &&sgn((b.p2 – b.p1) % (a.p1 – b.p1)) * sgn((b.p2 – b.p1) % (a.p2 – b.p1)) <= 0 ;}
此函数经过反复修改，这个方法是一个准确、效率较高的方法。但注意，不同题目线段相交的定义可能不同，比如有时不允许交点在端点，这个时候函数需要自行改动。而判断线段与直线相交，射线和线段相交等，也是在此函数拓展而来的。
此题代码
;ll;inline int read(){int x=0,f=1;char ch=getchar();while(ch>’9’||ch<‘0′){if(ch==’-‘)f=-1;ch=getchar();}while(ch>=’0’&&ch<=’9’){x=x*10+ch-‘0’;ch=getchar();}return x*f;}const double eps = 1e-9, pi = acos(-1.0);inline int sgn(double x){if(fabs(x) < eps) return 0;else return x > 0? 1 : -1;}struct Point{double x, y;Point(){};Point(double x1, double y1){x = x1, y = y1;}};typedef Point Vector;Vector operator + (const Vector a, const Vector b){return Vector(a.x + b.x, a.y + b.y);}Vector operator – (const Vector a, const Vector b){return Vector(a.x – b.x, a.y – b.y);}double operator * (const Vector a, const Vector b){return a.x * b.x + a.y * b.y;}double operator % (const Vector a, const Vector b){return a.x * b.y – a.y * b.x;}Vector operator * (const Vector a, const double b){return Vector(a.x * b, a.y * b);}Vector operator * (const double b, const Vector a){return Vector(a.x * b, a.y * b);}struct Seg{Point p1, p2;Seg(){};Seg(Point p11, Point p22){p1 = p11, p2 = p22;}};sgn((a.p2 – a.p1) % (b.p1 – a.p1)) * sgn((a.p2 – a.p1) % (b.p2 – a.p1)) <= 0 &&sgn((b.p2 – b.p1) % (a.p1 – b.p1)) * sgn((b.p2 – b.p1) % (a.p2 – b.p1)) <= 0 ;}int m, n;char grid[50][50];int val[50][50];struct Downto{int x, y;}downto[50][50];void Build_downto(){for(int j = 1; j <= n; j++){for(int i = m; i >= 1; i–){if(grid[i][j] == ‘#’) downto[i][j].x = i,downto[i][j].y = j;else{if(i == m) downto[i][j].x = m + 1, downto[i][j].y = j;else downto[i][j] = downto[i+1][j];}}}}struct Maze{Point p[6];int i, j;}maze[50][50];void Build_Maze(){for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){maze[i][j].i = i;maze[i][j].j = j;}}maze[1][1].p[0] = Point(1, -1);maze[1][1].p[1] = Point(0, 0);maze[1][1].p[2] = Point(2, 0);maze[1][1].p[3] = Point(2, -2);maze[1][1].p[4] = Point(0, -2);for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){if(i == 1 && j == 1) continue;if(j == 1){for(int k = 0; k <= 4; k++){maze[i][j].p[k] = maze[i-1][j].p[k] + Vector(0, -2);}}else{for(int k = 0; k <= 4; k++){maze[i][j].p[k] = maze[i][j-1].p[k] + Vector(2, 0);}}}}}bool dangzhu[31][31][31][31];bool dang(Point p1, Point p2, int minx, int maxx,int miny,int maxy){for(int j = miny; j <= maxy; j++){int xt = minx, yt = j;int x, y;x = downto[xt][yt].x;y = downto[xt][yt].y;while(x <= maxx){for(int k = 1; k <= 4; k++){int nexk = k == 4 ? 1: k + 1;if(Seg(maze[x][y].p[k], maze[x][y].p[nexk]) / Seg(p1 ,p2)){return true;}}x++;if(x > maxx) break;xt = x, yt = y;x = downto[xt][yt].x;y = downto[xt][yt].y;}}return false;}void Build_dangzhu(){for(int i1 = 1; i1 <= m; i1++){for(int j1 = 1; j1 <= n; j1++){if(grid[i1][j1] == ‘#’) continue;for(int i2 = i1; i2 <= m; i2++){for(int j2 = 1; j2 <= n; j2++){if(i2 == i1 && j2 <= j1) continue;if(grid[i2][j2] == ‘#’) continue;if(dang(maze[i1][j1].p[0], maze[i2][j2].p[0], min(i1,i2), max(i1,i2), min(j1,j2), max(j1,j2))){dangzhu[i1][j1][i2][j2] = true;dangzhu[i2][j2][i1][j1] = true;}}}}}}int vis[50][50],kase;void go(int initi, int initj){if(vis[initi][initj] != kase) vis[initi][initj] = kase, val[initi][initj] += 1;for(int i = initi – 1; i >=1 ;i–){if(grid[i][initj] == ‘#’) break;if(vis[i][initj] != kase) vis[i][initj] = kase, val[i][initj] += 1;}for(int i = initi + 1; i <= m ;i++){if(grid[i][initj] == ‘#’) break;if(vis[i][initj] != kase) vis[i][initj] = kase, val[i][initj] += 1;}for(int j = initj – 1; j >=1 ;j–){if(grid[initi][j] == ‘#’) break;if(vis[initi][j] != kase) vis[initi][j] = kase, val[initi][j] += 1;}for(int j = initj + 1; j <= n ;j++){if(grid[initi][j] == ‘#’) break;if(vis[initi][j] != kase) vis[initi][j] = kase, val[initi][j] += 1;}}struct Answer{int i, j;}ans[100010];int numans;bool cmpans(const Answer a, const Answer b){if(a.i != b.i) return a.i < b.i;else return a.j < b.j;}int main(){freopen(“jealous.in”,”r”,stdin);freopen(“jealous.out”,”w”,stdout);scanf(“%d%d”,&m,&n);for(int i = 1; i <= m; i++){scanf(“%s”,grid[i] + 1);}Build_Maze();Build_downto();Build_dangzhu();kase = 0;for(int i1 = 1; i1 <= m; i1++){for(int j1 = 1; j1 <= n; j1++){if(grid[i1][j1] == ‘#’) continue;kase++;for(int i2 = 1; i2 <= m; i2++){for(int j2 = 1; j2 <= n; j2++){if(grid[i2][j2] == ‘#’) continue;if(dangzhu[i1][j1][i2][j2]){go(i2, j2);}}}if(vis[i1][j1] == kase) val[i1][j1] –;}}int tot = 0;for(int i = 1; i <= m; i++){for(int j = 1; j<= n; j++){if(grid[i][j] == ‘.’) tot++;}}for(int i = 1; i <= m; i++){for(int j = 1; j<= n; j++){if(grid[i][j] == ‘.’ && val[i][j] == tot – 1){int t = ++numans;ans[t].i = i;ans[t].j = j;}}}if(numans > 0) sort(ans + 1, ans + 1 + numans, cmpans);printf(“%d\n”,numans);for(int i = 1; i <= numans; i++){printf(“%d %d\n”,ans[i].i, ans[i].j);}return 0;}
最有效的资本是我们的信誉，它24小时不停为我们工作。
