UVA 10531 Maze Statistics 迷宫统计迷宫插头DP 四联通概率

　　题意：

　　　　有一个N*M的图，每个格子有独立概率p变成障碍物。你要从迷宫左上角走到迷宫右下角。求每个格子成为一个有解迷宫中的障碍物的概率。N <= 5，M <= 6

　　分析：

　　　　这真是一道好题，网上几乎没有任何关于四连通的插头DP的任何资料，这道题目很好地反映了这类问题。

　　　　四连通中，只要你存在了右插头，必然存在下插头，当然，你的插头不一定需要真正连到可行格子中，因此在当前行中你只需要记录右插头。

　　　　但是不是需要换行的吗？由于下插头跟右插头是同时存在的，那么我们只需要把右插头当做下插头来用就可以了，是不是比普通的简单路径的插头dp简单很多？

　　　　来，我们看一下转移吧，其实情况的分类还是跟普通的插头dp一样的，不得不说cdq的插头普适性真是厉害。

　　　　1、同时存在左插头和上插头，那么只需要把连通块连一下，然后记一个右插头。

　　　　2、只存在左插头或者上插头，那么只需要延续连通块，再记一个右插头。

　　　　3、都不存在左插头和上插头，那么只需要新建一个连通块，记在右插头。

　　　　而换行操作，只需要把右插头变成下插头就可以了。

　　程序：（学习了某岛大神的代码之后才写出来了这份代码）

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <string>

 #include <algorithm>

 #include <iostream>

 using namespace std;

 typedef long long LL;

 const int HASH = ;

 const int STATE = ;

 const int MAXD = ;

 const double EPS = 1e-;

 int n, m;

 double maze[MAXD][MAXD];

 int code[MAXD], ch[MAXD];

 int fcmp(double x)

 {

     return x < -EPS ? - : x > EPS;

 }

 void decode(LL st)

 {

     int i;

     for (i = m; i >= ; --i)

     {

         code[i] = st&;

         st >>= ;

     }

 }

 LL encode()

 {

     LL st = ;

     int i, cnt = ;

     memset(ch, -, sizeof(ch));

     ch[] = , ch[] = ;

     for (i = ; i <= m; ++i)

     {

         if (ch[code[i]] == -)

             ch[code[i]] = ++cnt;

         code[i] = ch[code[i]];

         st <<= ;

         st |= code[i];

     }

     return st;

 }

 struct HASHMAP

 {

     int head[HASH], next[STATE], size;

     LL state[STATE];

     double f[STATE];

     void clear()

     {

         size = ;

         memset(head, -, sizeof(head));

     }

     void push(LL st, double ans)

     {

         int i;

         decode(st);

         for (i = ; i <= m; ++i)

             if (code[i] == )

                 break ;

         if (i == m+) //如果编号为1的连通块不存在，那就不可行

             return ;

         int x = st%HASH;

         for (i = head[x]; i != -; i = next[i])

             if (st == state[i])

             {

                 f[i] += ans;

                 return ;

             }

         f[size] = ans;

         state[size] = st;

         next[size] = head[x];

         head[x] = size ++;

     }

 }hm[];

 void in()

 {

     int i, j;

     scanf("%d %d", &n, &m);

     for (i = ; i <= n; ++i)

         for (j = ; j <= m; ++j)

             scanf("%lf", &maze[i][j]);

 }

 void dp_blank(int i, int j, int cur)

 {

     if (!fcmp(1.0-maze[i][j]))

         return ;

     int k, lef, up, t;

     for (k = ; k < hm[cur].size; ++k)

     {

         if (!fcmp(hm[cur].f[k]))

             continue ;

         decode(hm[cur].state[k]);

         lef = code[j-], up = code[j];

         if (lef && up)//分类讨论只对右插头做修改

         {

             if (lef != up)

             {

                 if (lef < up)

                     swap(lef, up);

                 for (t = ; t <= m; ++t)

                     if (code[t] == lef)

                         code[t] = up;

             }

         }

         else

         {

             if (lef || up)

                 code[j] = lef|up;

             else

                 code[j] = m+;

         }

         hm[cur^].push(encode(), hm[cur].f[k]*(1.0-maze[i][j]));

     }

 }

 void dp_block(int i, int j, int cur)

 {

     if (!fcmp(maze[i][j]))

         return ;

     int k;

     for (k = ; k < hm[cur].size; ++k)

     {

         if (!fcmp(hm[cur].f[k]))

             continue ;

         decode(hm[cur].state[k]);

         code[j] = ;//同理

         hm[cur^].push(encode(), hm[cur].f[k]*maze[i][j]);

     }

 }

 double solve()

 {

     int i, j, cur = ;

     memset(code, , sizeof(code));

     hm[cur].clear();

     code[] = ;

     hm[cur].push(encode(), );

     for (i = ; i <= n; ++i)

         for (j = ; j <= m; ++j)

         {

             hm[cur^].clear();

             dp_blank(i, j, cur);

             dp_block(i, j, cur);

             cur ^= ;

         }

     double ret = ;

     for (i = ; i < hm[cur].size; ++i)

     {

         decode(hm[cur].state[i]);

         if (code[m] == )

             ret += hm[cur].f[i];

     }

     return ret;

 }

 void work()

 {

     int i, j;

     double sum = solve();

     for (i = ; i <= n; ++i)

         for (j = ; j <= m; ++j)

         {

             double cache = maze[i][j];

             maze[i][j] = 1.0;

             printf("%.6lf%c", solve()*cache/sum, (j == m) ? '\n' : ' ');

             maze[i][j] = cache;

         }

 }

 int main()

 {

     int T, iCase = ;

     scanf("%d", &T);

     while (T --)

     {

         if (iCase++)

             printf("\n");

         in();

         work();

     }

     return ;

 }

巴特西

UVA 10531 Maze Statistics 迷宫统计迷宫插头DP 四联通概率

最新文章

热门文章

巴特西

UVA 10531 Maze Statistics 迷宫统计 迷宫插头DP 四联通 概率

最新文章

热门文章

UVA 10531 Maze Statistics 迷宫统计迷宫插头DP 四联通概率