题意：给定一个n*n的地图，上面有k个障碍点不能走，有一个机器人从(0,0)出发，每次等概率的不动或者往上下左右没有障碍的地方走动，问走无限步后停在图的右下部的概率
n<=1e4，k<=1e3
思路：据说是找规律
From https://blog.csdn.net/anna__1997/article/details/78494788 牛逼的证明
马尔科夫链的随机游走模型
-
可建立状态转移矩阵，对n * n 的图中n * n 个点编号为0 ~[ (n - 1) * n + n – 1] 设最大编号为max
P = p(i, j) = [p(0, 0) p(0, 1) … p(0, max)
P(1, 0) p(1, 1) … p(1, max)
…
P(max, 0) p(max, 1) … p(max, max)]
π(i) 为i时间各点的概率
π(n + 1) = π(n) * P
当时间->无穷 π(n + 1)->π
可以通过 π * P = π 计算
验证猜测结果正确
*******************************************************
找规律的答案 有待证明
现在能想到的是 整个封闭系统每个格子以出现机器人的概率作为权值 在很长的时间线上是一个熵增的
过程(想到元胞自动机)，如果要模拟这个概率扩散的过程的话，格子的权值的更新是一个用他所能到达的格子的权值
和他自身的权值迭代的过程，这个过程中可以发现他的相邻的格子的权值是在不断同化的，因此，在无穷远后
(0, 0)的和他周围的格子的权值不在体现优势，而更加开放的格子则更占优(可根据迭代公式理解)
*******************************************************
考虑每个障碍点对答案的影响，找规律后的得到只与障碍点所在的位置与周围的联通情况有关
判格子是不是障碍可以用set
1 #include<cstdio> 2 #include<cstring> 3 #include<string> 4 #include<cmath> 5 #include<iostream> 6 #include<algorithm> 7 #include<map> 8 #include<set> 9 #include<queue> 10 #include<vector> 11 using namespace std; 12 typedef long long ll; 13 typedef unsigned int uint; 14 typedef unsigned long long ull; 15 typedef pair<int,int> PII; 16 typedef vector<int> VI; 17 #define fi first 18 #define se second 19 #define MP make_pair 20 #define N 11000 21 #define M 210 22 #define MOD 1e9+7 23 #define eps 1e-8 24 #define pi acos(-1) 25 int dx[]={0,-1,1,0,0},dy[]={0,0,0,-1,1}; 26 set<int>st; 27 28 29 int read() 30 { 31 int v=0,f=1; 32 char c=getchar(); 33 while(c<48||57<c) {if(c=='-') f=-1; c=getchar();} 34 while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar(); 35 return v*f; 36 } 37 38 int gcd(int x,int y) 39 { 40 if(y==0) return x; 41 return gcd(y,x%y); 42 } 43 44 int main() 45 { 46 //freopen("hdoj6229.in","r",stdin); 47 //freopen("hdoj6299.out","w",stdout); 48 int cas; 49 scanf("%d",&cas); 50 for(int v=1;v<=cas;v++) 51 { 52 st.clear(); 53 int n,m; 54 scanf("%d%d",&n,&m); 55 for(int i=1;i<=m;i++) 56 { 57 int x,y; 58 scanf("%d%d",&x,&y); 59 st.insert(x*N+y); 60 } 61 int s1=n*n*5-n*4; 62 int s2=n*(n+1)/2*5-2*n-2; 63 set<int>::iterator t=st.begin(); 64 while(t!=st.end()) 65 { 66 int s=*t; 67 int x=s/N; 68 int y=s%N; 69 for(int i=1;i<=4;i++) 70 { 71 int tx=x+dx[i]; 72 int ty=y+dy[i]; 73 if(tx<0||tx>=n||ty<0||ty>=n||st.count(tx*N+ty)) continue; 74 s1--; 75 if(tx+ty>=n-1) s2--; 76 } 77 78 if(x+y>=n-1) 79 { 80 s2-=5; 81 if(x==0||x==n-1) s2++; 82 if(y==0||y==n-1) s2++; 83 } 84 85 s1-=5; 86 if(x==0||x==n-1) s1++; 87 if(y==0||y==n-1) s1++; 88 t++; 89 } 90 91 int k=gcd(s1,s2); 92 printf("Case #%d: %d/%d ",v,s2/k,s1/k); 93 } 94 return 0; 95 } 96