BZOJ1698: [Usaco2007 Feb]Lilypad Pond 荷叶池塘

一傻逼题调了两天。。

n<=30 * m<=30的地图，0表示可以放平台，1表示本来有平台，2表示不能走，3起点4终点，走路方式为象棋的日字，求：从起点走到终点，至少要放多少平台，以及放平台的方案数，无解-1。

方法一：其实能走直接平台的就可以直接走来走去，也就是算一个联通块。类似于tarjan，先把一大块缩成一点，然后连边走最短路。

错误！存在边权为0的边，会导致统计方案出现重复。比如：

圆圈走到三角形，直接走和绕一圈是一样的，但算了两次。

方法二：把0边去掉就行了。由于数据小，开个数组[a][b][c][d]表示a,b到c,d是否能通过填一块到达，这个数组只需对每个点做一次搜索就能出来。最后就是最短路啦。

不过边权为1，谁最短路会写迪杰呢？肯定bfs啦！

 #include<stdio.h>

 #include<string.h>

 #include<stdlib.h>

 #include<algorithm>

 //#include<iostream>

 using namespace std;

 int n,m;

 int a[][],can[][][][];

 #define maxn 1011

 #define maxm 10011

 struct Edge{int tx,ty,next;}edge[maxn*maxn];int first[][],le=;

 #define LL long long

 void in(int sx,int sy,int tx,int ty)

 {

     Edge &e=edge[le];

     e.tx=tx;e.ty=ty;

     e.next=first[sx][sy];

     first[sx][sy]=le++;

 }

 int nx,ny;

 const int dx[]={,,,,-,-,-,-},dy[]={,-,,-,,-,,-};

 bool vis[][];

 void dfs(int x,int y)

 {

     vis[x][y]=;

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

     {

         const int xx=x+dx[i],yy=y+dy[i];

         if (xx< || xx>n || yy< || yy>m || can[nx][ny][xx][yy]

         || a[xx][yy]== || vis[xx][yy]) continue;

         if (a[xx][yy]== || a[xx][yy]==)

         {

             can[nx][ny][xx][yy]=;

             continue;

         }

         dfs(xx,yy);

     }

 }

 const int inf=0x3f3f3f3f;

 int dis[][];LL way[][];

 struct qnode{int x,y;}q[maxn];int head,tail;

 void bfs(int sx,int sy)

 {

     head=;tail=;q[].x=sx;q[].y=sy;

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

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

             dis[i][j]=inf;

     dis[sx][sy]=;way[sx][sy]=;

     while (head!=tail)

     {

         const int nx=q[head].x,ny=q[head++].y;

         for (int i=first[nx][ny];i;i=edge[i].next)

         {

             const Edge &e=edge[i];

             if (dis[e.tx][e.ty]>dis[nx][ny]+)

             {

                 dis[e.tx][e.ty]=dis[nx][ny]+;

                 way[e.tx][e.ty]=way[nx][ny];

                 q[tail].x=e.tx,q[tail++].y=e.ty;

             }

             else if (dis[e.tx][e.ty]==dis[nx][ny]+)

                 way[e.tx][e.ty]+=way[nx][ny];

         }

     }

 }

 int main()

 {

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

     int sx,sy,tx,ty;

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

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

         {

             scanf("%d",&a[i][j]);

             if (a[i][j]==) sx=i,sy=j;

             if (a[i][j]==) tx=i,ty=j;

         }

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

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

         {

             memset(can[i][j],,sizeof(can[i][j]));

             memset(vis,,sizeof(vis));

             if (a[i][j]==) continue;

             nx=i;ny=j;

             dfs(i,j);

         }

     memset(first,,sizeof(first));

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

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

             for (int k=;k<=n;k++)

                 for (int l=;l<=m;l++)

                 {

                     if (can[i][j][k][l])

                     {

                         in(i,j,k,l);

                     }

                 }

     bfs(sx,sy);

     if (dis[tx][ty]==inf) puts("-1");

     else printf("%d\n%lld\n",dis[tx][ty]-,way[tx][ty]);

     return ;

 }