Description
为了让奶牛们娱乐和锻炼，农夫约翰建造了一个美丽的池塘。这个长方形的池子被分成了M行N列个方格（1≤M,N≤30）。一些格子是坚固得令人惊讶的莲花，还有一些格子是岩石，其余的只是美丽、纯净、湛蓝的水。
贝西正在练习芭蕾舞，她站在一朵莲花上，想跳到另一朵莲花上去，她只能从一朵莲花跳到另一朵莲花上，既不能跳到水里，也不能跳到岩石上。
贝西的舞步很像象棋中的马步：每次总是先横向移动一格，再纵向移动两格，或先纵向移动两格，再横向移动一格。最多时，贝西会有八个移动方向可供选择。
约翰一直在观看贝西的芭蕾练习，发现她有时候不能跳到终点，因为中间缺了一些荷叶。于是他想要添加几朵莲花来帮助贝西完成任务。一贯节俭的约翰只想添加最少数量的莲花。当然，莲花不能放在石头上。
请帮助约翰确定必须要添加的莲花的最少数量，以及有多少种放置这些莲花的方法.
第一行：两个用空格分开的整数：M和N
第二行到M+1行：第i+1行有N个用空格分开的整数，描述了池塘第i行的状态：
0为水，1为莲花，2为岩石，3为贝西所在的起点，4为贝西想去的终点。
Output
第一行：一个整数，需要增加的最少莲花数；如果无解，输出-1。
第二行：放置这些莲花的方案数量，保证这个数字不会超过一个64位的有符号整数，
如果第一行是-1，不要输出第二行。
4 5 1 0 0 0 0 3 0 0 0 0 0 0 2 0 0 0 0 0 4 0
Sample Output
2 3
想法
这个题还是挺好玩的。 看到这个题后我的第一反应是dp，就是记f[i]为这个点到终点要添加的最少莲花数，转移就枚举所有i能一次跳到的点j，若该点为水则f[i]=f[j]+1，否则f[i]=f[j] 然后发现这样其实就是建了一张图，每个点向一次能跳到的点连边，若它跳到的那个点为水则边权为1，否则边权为0 这样跑一个最短路就是需要添加的最少莲花数
然后考虑怎么计数。 首先需要意识到，题目要求的是放莲花的方案，而不是上图最短路的数量 那么我们可以尝试把所有0边都删掉，在剩下的边权都为1的图中最短路数量便是放莲花方案数 怎么删0边呢，其实就是把通过0边连起来的两个点直接连一条边就行了 换句话说，就是每一个点向它在添加一次莲花后可跳到的点连边，原本有莲花的点就不放在新图中了 跑个最短路计数就好了
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#define INF 100000000
using namespace std;
typedef long long ll;
const int N = 40;
const int M = N*N;
struct node{
int v;
node *next;
}pool[M*1000],*h[M];
int cnt;
void addedge(int u,int v){
node *p=&pool[++cnt];
p->v=v;p->next=h[u];h[u]=p;
}
queue<int> que;
ll d[M],num[M];
int vis[M];
int S,T,n,m;
ll get(int u){
if(num[u]) return num[u];
int v;
for(node *p=h[u];p;p=p->next)
if(d[v=p->v]==d[u]-1) num[u]+=get(v);
return num[u];
}
void spfa(){
int u,v;
while(!que.empty()) que.pop();
for(int i=1;i<=n*m;i++) d[i]=INF;
que.push(S); vis[S]=1; d[S]=0;
while(!que.empty()){
u=que.front(); que.pop();
for(node *p=h[u];p;p=p->next)
if(d[v=p->v]>d[u]+1){
d[v]=d[u]+1;
if(!vis[v]) { que.push(v); vis[v]=1; }
}
vis[u]=0;
}
num[S]=1;
for(int i=1;i<=n*m;i++)
if(!num[i]) get(i);
}
int map[N][N],dre[8][2]={-2,-1,-2,1,-1,-2,-1,2,1,-2,1,2,2,-1,2,1};
int used[N][N];
bool check(int x,int y){ return x>0 && x<=n && y>0 && y<=m; }
void add(int id,int x,int y){
int xx,yy;
used[x][y]=id;
for(int i=0;i<8;i++)
if(check(xx=x+dre[i][0],yy=y+dre[i][1])){
if(used[xx][yy]==id || map[xx][yy]==2) continue;
used[xx][yy]=id;
if(map[xx][yy]==1) add(id,xx,yy);
else addedge(id,(xx-1)*m+yy);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) {
scanf("%d",&map[i][j]);
if(map[i][j]==3) S=(i-1)*m+j;
else if(map[i][j]==4) T=(i-1)*m+j;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) if(map[i][j]!=1 && map[i][j]!=2) add((i-1)*m+j,i,j);
spfa();
if(d[T]==INF) printf("-1\n");
else printf("%lld\n%lld\n",d[T]-1,num[T]);
return 0;
}
转载于:https://www.cnblogs.com/lindalee/p/8898047.html
相关资源：数据结构—成绩单生成器
