【HDOJ6229】Wandering Robots（马尔科夫链，set）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题意：给定一个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

  #include<cstdio>
  #include<cstring>
  #include<string>
  #include<cmath>
  #include<iostream>
  #include<algorithm>
  #include<map>
  #include<set>
  #include<queue>
  #include<vector>
  using namespace std;
  typedef long long ll;
  typedef unsigned int uint;
  typedef unsigned long long ull;
  typedef pair<int,int> PII;
  typedef vector<int> VI;
  #define fi first
  #define se second
  #define MP make_pair
  #define N 11000
  #define M 210
  #define MOD 1e9+7
  #define eps 1e-8
  #define pi acos(-1)
  int dx[]={,-,,,},dy[]={,,,-,};
  set<int>st; int read()
  {
  int v=,f=;
  char c=getchar();
  while(c<||<c) {if(c=='-') f=-; c=getchar();}
  while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();
  return v*f;
  } int gcd(int x,int y)
  {
  if(y==) return x;
  return gcd(y,x%y);
  } int main()
  {
  //freopen("hdoj6229.in","r",stdin);
  //freopen("hdoj6299.out","w",stdout);
  int cas;
  scanf("%d",&cas);
  for(int v=;v<=cas;v++)
  {
  st.clear();
  int n,m;
  scanf("%d%d",&n,&m);
  for(int i=;i<=m;i++)
  {
  int x,y;
  scanf("%d%d",&x,&y);
  st.insert(x*N+y);
  }
  int s1=n*n*-n*;
  int s2=n*(n+)/*-*n-;
  set<int>::iterator t=st.begin();
  while(t!=st.end())
  {
  int s=*t;
  int x=s/N;
  int y=s%N;
  for(int i=;i<=;i++)
  {
  int tx=x+dx[i];
  int ty=y+dy[i];
  if(tx<||tx>=n||ty<||ty>=n||st.count(tx*N+ty)) continue;
  s1--;
  if(tx+ty>=n-) s2--;
  } if(x+y>=n-)
  {
  s2-=;
  if(x==||x==n-) s2++;
  if(y==||y==n-) s2++;
  } s1-=;
  if(x==||x==n-) s1++;
  if(y==||y==n-) s1++;
  t++;
  } int k=gcd(s1,s2);
  printf("Case #%d: %d/%d\n",v,s2/k,s1/k);
  }
  return ;
  }