一傻逼题调了两天。。
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 ;
}