记录编号	321891	评测结果	AAAAAAAAAAAAAA
题目名称	[USACO Feb07] 银色莲花池	最终得分	100
用户昵称	LOSER	是否通过	通过
代码语言	C++	运行时间	0.156 s
提交时间	2016-10-14 07:51:32	内存使用	21.13 MiB

/*
	Name: 银色莲花池 
	Author: LOSER ! ! !   
	Date: 14/10/16 07:42
	Description: 
		前两问很好解决 一遍宽搜可以很好的解决问题
		但是关键在第三问 要求输出方案(记住这一个教训方案数很可能需要开longlong甚至是写高精度)
		开始时想的是一遍宽搜跑出答案但这显然不现实 因为vis数组会很好的帮你去重
		于是又想到了用一个f[x][y][step][ned]表示在一个点用step布 添加ned荷叶的方案数虽然这可以很好的
		计算所有情况,但是也很好的超过了内存限制,迫不得已看了一下题解 -_-|||
		由于是最短距离到达终点 所以我们可以用 dis[x][y][ned] 表示用ned荷叶到达(x,y) 所用的最短距离
		way[x][y][ned] 表示方案数 于是乎得出了答案 
*/
#include <queue> 
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 35
#define maxm maxn*maxn
#define LL long long
#define inf 0x7f7f7f7f
LL n,m,ans=inf,num=inf,cnt,a[maxn][maxn],startx,starty,endx,endy;
LL st[8][2]={{-2,1},{-1,2},{2,1},{1,2},{-2,-1},{-1,-2},{1,-2},{2,-1}};
struct Node{
	LL x,y,step,ned;
	Node(LL A,LL B,LL C,LL D){
		x=A,y=B,step=C,ned=D;
	}
};
queue<Node> q;
bool vis[maxn][maxn][maxm],Check;
LL dis[maxn][maxn][maxm],way[maxn][maxn][maxm];
void Bfs(){
	while( !q.empty() ){
		Node temp=q.front(); q.pop();
		if(temp.ned>num) continue;
		for(LL i=0;i<8;i++){
			LL xx=temp.x+st[i][0],yy=temp.y+st[i][1];
			if(xx<1||yy<1||xx>n||yy>m)continue;
			if(a[xx][yy]==2)continue;
			if(a[xx][yy]==4){
				Check=1;
				if(num>temp.ned){
					num=temp.ned;
					ans=temp.step+1;
					continue;
				}
				if(num==temp.ned){
					if(ans>temp.step+1){
						ans=temp.step+1;
						continue;
					}
				}
			}
			if(a[xx][yy]==1 && !vis[xx][yy][temp.ned]){				
				q.push(Node(xx,yy,temp.step+1,temp.ned));
				vis[xx][yy][temp.ned]=1;
			}
			if(a[xx][yy]==0 && !vis[xx][yy][temp.ned+1] ){
				q.push(Node(xx,yy,temp.step+1,temp.ned+1));
				vis[xx][yy][temp.ned+1]=1;
			}
		}
	}
	if(!Check) {printf("-1\n-1\n-1\n"); exit(0);}
	while( !q.empty() )q.pop();
	for(LL i=1;i<=n;i++)for(LL j=1;j<=m;j++)for(LL k=0;k<=num;k++) dis[i][j][k]=inf;
	memset(dis[startx][starty],0,sizeof(dis[startx][starty]));
	memset(way,0,sizeof(way));  way[startx][starty][0]=1;
	q.push(Node(startx,starty,0,0));
	a[endx][endy]=1;
	while( !q.empty() ){
		Node temp=q.front();q.pop();
		for(LL i=0;i<8;i++){
			LL xx=temp.x+st[i][0],yy=temp.y+st[i][1];
			if(xx<1||yy<1||xx>n||yy>m)continue;
			if(a[xx][yy]==2)continue;
			if(a[xx][yy]==1){
				if(temp.step+1<=ans && temp.ned<=num){
					if(temp.step+1<=dis[xx][yy][temp.ned]){
						if(temp.step+1<dis[xx][yy][temp.ned]){
							q.push(Node(xx,yy,temp.step+1,temp.ned));
							way[xx][yy][temp.ned]=0;
						}
						way[xx][yy][temp.ned]+=way[temp.x][temp.y][temp.ned];
						dis[xx][yy][temp.ned]=temp.step+1;
					}
				}
			}
			if(a[xx][yy]==0){
				if(temp.ned+1<=num && temp.step+1<=ans){
					if(temp.step+1<=dis[xx][yy][temp.ned+1]){
						if(temp.step+1<dis[xx][yy][temp.ned+1]){
							q.push(Node(xx,yy,temp.step+1,temp.ned+1));
							way[xx][yy][temp.ned+1]=0;
						}
						way[xx][yy][temp.ned+1]+=way[temp.x][temp.y][temp.ned];
						dis[xx][yy][temp.ned+1]=temp.step+1;		
					}
				}
			}
		}
	}
}
int main(){
	freopen("silvlily.in","r",stdin); freopen("silvlily.out","w",stdout);
	scanf("%lld%lld",&n,&m);
	LL x,y;
	for(LL i=1;i<=n;i++){
		for(LL j=1;j<=m;j++){
			scanf("%lld",&a[i][j]);
			if(a[i][j]==3){
				q.push(Node(i,j,0,0));
				vis[i][j][0]=1; startx=i;starty=j;
			}
			if(a[i][j]==4){endx=i,endy=j;}
		}
	}
	Bfs();
	printf("%lld\n%lld\n%lld\n",num,ans,way[endx][endy][num]);
	getchar(); getchar();
	return 0;
}