Description：

$N\times M$ 的矩阵，有些位置可以踩，有些位置不能踩，还有些位置不能放可以踩的，问最少放几个可以踩的位置可以从起点走到终点，以及放的方案数。

$1\le N,M\le 30$

Solution：

把可以踩看成边权为 $0$ 的边，不能踩不建边，放可以踩的看成边权为一的边，那第一问就是最短路，但是由于有 $0$ 边的存在，不同的最短路可能代表同一种摆放方式，于是考虑把 $0$ 边去掉，即 $BFS$ 找到所有一步可达的位置向这些位置建边权为一的边，最后跑最短路计数即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 35

int p[MAXN][MAXN];

int mx[8] = {-1,-2,-2,-1,1,2,2,1};

int my[8] = {-2,-1,1,2,2,1,-1,-2};

int to(int i,int j){return (i - 1) * m + j;}

int s,t;

struct edge

{

	int to,nxt,v;

}e[MAXN * MAXN * 100];

int edgenum = 0;

int lin[MAXN * MAXN] = {0};

void add(int a,int b,int c)

{//cout << a << " " << b << " " << c << endl; 

	++edgenum;e[edgenum].to = b;e[edgenum].v = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	return;

}

#define fi first

#define se second

bool v[MAXN][MAXN];

void BFS(int x,int y)

{

	queue< pair<int,int> > q;q.push(make_pair(x,y));

	memset(v,false,sizeof(v));

	while(!q.empty())

	{

		pair<int,int> k = q.front();q.pop();

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

		{

			if(v[k.fi + mx[i]][k.se + my[i]])continue;

			if(k.fi + mx[i] < 1 || k.fi + mx[i] > n || k.se + my[i] < 1 || k.se + my[i] > m)continue;

			if(p[k.fi + mx[i]][k.se + my[i]] == 0)add(to(x,y),to(k.fi + mx[i],k.se + my[i]),1);

			if(p[k.fi + mx[i]][k.se + my[i]] == 1)q.push(make_pair(k.fi + mx[i],k.se + my[i]));

			v[k.fi + mx[i]][k.se + my[i]] = true;

		}

	}

	return;

}

typedef long long ll;

ll d[MAXN * MAXN],cnt[MAXN * MAXN];

bool inq[MAXN * MAXN];

int main()

{

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

	memset(p,-1,sizeof(p));

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

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

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

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

	{

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

		{

			if(p[i][j] == 3)

			{

				s = to(i,j);

				p[i][j] = 0;

			}

			if(p[i][j] == 4)

			{

				t = to(i,j);

				p[i][j] = 0;

			}

		}

	}

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

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

			if(p[i][j] == 0)BFS(i,j);

	memset(d,0x3f,sizeof(d));d[s] = 0;

	memset(cnt,0,sizeof(cnt));cnt[s] = 1;

	memset(v,false,sizeof(v));

	queue<int> q;q.push(s);

	while(!q.empty())

	{

		int k = q.front();q.pop();

		inq[k] = false;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(d[e[i].to] > d[k] + e[i].v)

			{

				d[e[i].to] = d[k] + e[i].v;

				cnt[e[i].to] = 0;

				if(!inq[e[i].to])

				{

					inq[e[i].to] = true;

					q.push(e[i].to);

				}

			}

			if(d[e[i].to] == d[k] + e[i].v)

			{

				cnt[e[i].to] += cnt[k];

			}

		}

	}

	if(cnt[t] == 0)puts("-1");

	else printf("%lld\n%lld\n",d[t] - 1,cnt[t]);

	return 0;

}