题目链接：Wandering Robots
题解：先讲一下规律，对于每一个格子它可以从多少个地方来有一个值（可以从自己到自己），然后答案就是统计合法格子上的数与所有格子的数的比值
比如说样例的3 0格子上的值就是
3 4 3
4 5 4
3 4 3
答案就是22/33 =2/3；接下来就是如何统计答案了，由于图1e4*1e4的但点只有1e3必须将图离散化得到新图，离散化是要将点相邻的两行也要加进新图,这样省去的点在原图上相邻没有被阻隔的点，然后dfs一次，把可以到达的点标记一边，然后统计答案注意边界。
#include<bits/stdc++.h> #define ll long long using namespace std; const int N=3e3+10; bool vis[N][N],mp[N][N]; int dx[]={0,1,0,-1}; int dy[]={1,0,-1,0}; int n,k,mm,mn; int sc[N],sr[N],cn1,cn2; int x[N],y[N]; int x_hash(int x) { return lower_bound(sc,sc+mn,x)-sc; } int y_hash(int y) { return lower_bound(sr,sr+mm,y)-sr; } void dfs(int x,int y) { vis[x][y]=1; for(int i=0;i<4;i++) { int tx=x+dx[i],ty=y+dy[i]; if(tx>=0&&tx<mn&&ty>=0&&ty<mm&&!vis[tx][ty]&&!mp[tx][ty])dfs(tx,ty); } } int get(int x,int y) { if(!vis[x][y])return 0; int cnt=vis[x][y]; for(int i=0;i<4;i++) { int tx=x+dx[i],ty=y+dy[i]; if(tx>=0&&tx<mn&&ty>=0&&ty<mm)cnt+=vis[tx][ty]; } return cnt; } int main(){ int T; scanf("%d",&T); int cas=1; while(T--) { cn1=0;cn2=0; //memset(vis,0,sizeof(vis)); //memset(mp,0,sizeof(mp)); scanf("%d %d",&n,&k); sc[cn1++]=0;sc[cn1++]=n-1; sr[cn2++]=0;sr[cn2++]=n-1; for(int i=0;i<k;i++) { scanf("%d %d",&x[i],&y[i]); sc[cn1++]=x[i];if(x[i]-1>=0)sc[cn1++]=x[i]-1;if(x[i]+1<n)sc[cn1++]=x[i]+1; sr[cn2++]=y[i];if(y[i]-1>=0)sr[cn2++]=y[i]-1;if(y[i]+1<n)sr[cn2++]=y[i]+1; } sort(sc,sc+cn1);sort(sr,sr+cn2); mn=unique(sc,sc+cn1)-sc;mm=unique(sr,sr+cn2)-sr; for(int i=0;i<=mn;i++) { for(int j=0;j<=mm;j++) { vis[i][j]=mp[i][j]=0; } } for(int i=0;i<k;i++) { mp[x_hash(x[i])][y_hash(y[i])]=1; } dfs(0,0); int an1=0,an2=0; for(int i=0;i<mn;i++) { if(i!=0) { an1+=(sc[i-1]+1+sc[i]+1)*(sc[i]-sc[i-1]-1)*5/2; an1-=sc[i]-sc[i-1]-1; } for(int j=0;j<mm;j++) { if(sr[j]+sc[i]>=n-1)an1+=get(i,j); if(j<mm-1&&sr[j]+1!=sr[j+1]) { int tmp=n-1-sc[i]; if(sr[j+1]-1>=tmp) { if(sr[j]+1>=tmp) { if(sc[i]==0||sc[i]==n-1)an1+=4*(sr[j+1]-sr[j]-1); else an1+=5*(sr[j+1]-sr[j]-1); } else { if(sc[i]==0||sc[i]==n-1)an1+=4*(sr[j+1]-tmp); else an1+=5*(sr[j+1]-tmp); } } } an2+=get(i,j); } } an2+=5*(n*n-mn*mm); an2-=2*(n-mn)+2*(n-mm); int gc=__gcd(an1,an2); an1/=gc;an2/=gc; printf("Case #%d: %d/%d ",cas++,an1,an2); } return 0; }