bzoj1698 [Usaco2007 Feb]Lilypad Pond 荷叶池塘 [BFS]

Description为了便于牛们欣赏和锻炼，农夫JOHN在他的农场上新添加了一个美丽的池塘。 JOHN的池塘是一个长方形，他已经把它划分成了M行N列的小正方行 (1 <= M <= 30; 1 <= N <= 30). 某些正方行里是石头，另外一些则是特别结实的荷叶，其余则只有清水。 为了锻炼，Bessie想从一片荷叶跳到另外一片。她的每一次跳跃都是一个象棋中的马步：两行一列或一行两列。 JOHN看到了Bessie并且发现有时Bessie没有办法达到她的目标荷叶。他准备添加一些荷叶来让Bessie完成她的目标。当然，荷叶不能放在石头上。 帮助JOHN找出他最少要放多少片荷叶和他一共有多少种放最少片荷叶的方案。Input第1行： 两个整数， M 和 N。第2~M+1行： 第i+1包含N个数，分别为第i行的N个格子的情况。 0表示格子为空，1表示有一片荷叶，2表示格子里有石头，3表示此格子是Bessie的起点，4 表示此格子是Bessie的目标。Output第1行： 一个数，最少情况下需要添加的荷叶数目。如果没有方案存在，输出- 1。第2行： 一个数，达到最小值的方案总数。这个数保证不超过内设64位整数(long long/ int64)的大小。如果第一行是-1，不要输出此行。Sample Input4 51 0 0 0 03 0 0 0 00 0 2 0 00 0 0 4 0输入解释：池塘含4行5列。Bessie在第2行第1列并且想跳到第4行第4列。池塘里有1块石头和3片荷叶。Sample Output23输出解释：至少需要2片荷叶。一共有三种摆法：第4行第2列，第2行第3列第1行第3列，第3行第2列第1行第3列，，第2行第5列 R1C2,R2C3 | R1C3,R3C2 | R1C3,R2C5 1 0 0 0 0 | 1 0 X 0 0 | 1 0 X 0 0 3 0 X 0 0 | 3 0 0 0 0 | 3 0 0 0 X 0 0 2 0 0 | 0 X 2 0 0 | 0 0 2 0 0 0 X 0 4 0 | 0 0 0 4 0 | 0 0 0 4 0Solution

先说第一问：最少加几片荷叶。 很简单建图然后跑spfa： 每个点向8个方向连边，如果点是清水，则边权为1，如果是荷叶则边权为0。起点和终点都视为清水，最后答案-1即可。

第一问没什么难度，重点说第二问：有几种添荷叶的方案。 首先如果要求的是到终点的最短路径条数怎么做？只要在spfa松弛的时候判断一下:

if (dist[cur] + value == dist[nex]) {tot[nex] += tot[cur];push();}if (dist[cur] + value < dist[nex]) {dist[nex] = dist[cur] + value;tot[nex] = tot[nex];push();}

但是这样求出的是“最短路径条数”，而不是“添加荷叶的方案数”，因为原图中有荷叶。这样我们就要改变建图的方式：

就是这样，spfa的代码都不用改。 唉我这傻逼这么一道题写了两天。。。

;struct Edge{int to, v;Edge() {}Edge(int a, int b) : to(a), v(b) {}};int n, m;int map[35][35];vector<Edge> edges[1005];int sx, sy, ex, ey;int dir[8][2] = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};bool check(int x, int y) {if (x < 0 || x >= n || y < 0 || y >= m) return false;if (map[x][y] == 2) return false;return true;}int dist[1005];long long ans[1005];bool vis[1005];void bfs() {queue<int> q;memset(dist, 0x3f, sizeof(dist));memset(ans, 0, sizeof(ans));memset(vis, 0, sizeof(vis));int s = sx * m + sy;q.push(s);dist[s] = 0;ans[s] = 1;vis[s] = 1;while (!q.empty()) {int cur = q.front();q.pop();for (int i = 0; i < edges[cur].size(); i++) {Edge e = edges[cur][i];if (dist[cur] + e.v == dist[e.to]) {ans[e.to] += ans[cur];if (!vis[e.to]) {if (e.to != ex * m + ey) {vis[e.to] = 1;q.push(e.to);}}}if (dist[cur] + e.v < dist[e.to]) {dist[e.to] = dist[cur] + e.v;ans[e.to] = ans[cur];if (!vis[e.to]) {if (e.to != ex * m + ey) {vis[e.to] = 1;q.push(e.to);}}}}}}int tmp[1005], tot = 0;int vis2[1005];int used[1005][1005];void dfs(int x, int y) {for (int i = 0; i < 8; i++) {int nx = x + dir[i][0];int ny = y + dir[i][1];if (!check(nx, ny)) continue;if (!map[nx][ny] && !vis2[nx * m + ny]) {vis2[nx * m + ny] = 1;tmp[tot++] = nx * m + ny;}if (map[nx][ny] == 1 && !vis[nx * m + ny]) {vis[nx * m + ny] = 1;dfs(nx, ny);}}}int main() {scanf(“%d %d”, &n, &m);int t;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {scanf(“%d”, &map[i][j]);if (map[i][j] == 3) {sx = i;sy = j;map[i][j] = 0;}if (map[i][j] == 4) {ex = i;ey = j;map[i][j] = 0;}}}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (map[i][j]) continue;for (int k = 0; k < 8; k++) {int nx = i + dir[k][0];int ny = j + dir[k][1];if (check(nx, ny) && !map[nx][ny])edges[i * m + j].push_back(Edge(nx * m + ny, 1));}}}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (map[i][j] == 1 && !vis[i * m + j]) {tot = 0;memset(vis2, 0, sizeof(vis2));vis[i * j + 1] = 1;dfs(i, j);for (int k = 0; k < tot; k++) {for (int l = k + 1; l < tot; l++) {if (!used[tmp[k]][tmp[l]]) {used[tmp[k]][tmp[l]] = used[tmp[l]][tmp[k]] = 1;edges[tmp[k]].push_back(Edge(tmp[l], 1));edges[tmp[l]].push_back(Edge(tmp[k], 1));}}}}}}bfs();if (dist[ex * m + ey] == 0x3f3f3f3f) {printf(“-1\n”);return 0;}printf(“%d\n%lld\n”, dist[ex * m + ey] – 1, ans[ex * m + ey]);return 0;}

带着感恩的心启程，学会爱，爱父母，爱自己，爱朋友，爱他人。