BFS模板题
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1372
思路：
这题就思路来说，DFS和BFS都可以得到最优解，不过dfs会生成大量重复非最优解，即使优化（用一个二维数组保存到每格的最短时间）也会超时。
下面先附上dfs代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
int sx, sy, ex, ey, ans = 64;
int vis[10][10];
int mov[8][2] = {
{-2,+1},{-1,+2},{+1,+2},{+2,+1},{+2,-1},{+1,-2},{-1,-2},{-2,-1}};bool get(int x, int y){if (x == ex&&y == ey) return true;return false;
}bool over(int x, int y){if (x<0||x>=8||y<0||y>=8) return true;return false;
}void dfs(int cur, int x, int y){if (cur >= ans) return;if (!vis[x][y]) vis[x][y] = cur;if (get(x, y)){ans = ans<cur?ans:cur;return;}for (int i = 0; i < 8; i++){if (!over(x+mov[i][0], y+mov[i][1])&&cur<=vis[x][y]){vis[x][y] = cur;dfs(cur+1, x+mov[i][0], y+mov[i][1]);}}
}int main()
{freopen("E://in.txt", "r", stdin);char s1, s2, mid;while(scanf("%c%d%c%c%d", &s1, &sy, &mid, &s2, &ey) != EOF){getchar();sy -= 1;ey -= 1;sx = s1 - 'a';ex = s2 - 'a';dfs(0, sx, sy);printf("To get from %c%d to %c%d takes %d knight moves.\n",s1, sy+1, s2, ey+1, ans);ans = 64;memset(vis, 0, sizeof(vis));}return 0;
}
用BFS就是一道很简单的模板题了
下面是AC代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;int sx, sy, ex, ey, ans;
int vis[10][10];
int mov[8][2] = {
{-2,+1},{-1,+2},{+1,+2},{+2,+1},{+2,-1},{+1,-2},{-1,-2},{-2,-1}};typedef struct point{int cur;int x;int y;
}point;bool get(int x, int y){if (x == ex&&y == ey) return true;return false;
}bool over(int x, int y){if (x<0||x>=8||y<0||y>=8) return true;return false;
}int bfs(){queue<point>q;point sta = {
0, sx, sy};q.push(sta);while(!q.empty()){point now = q.front();q.pop();if (get(now.x, now.y)){ans = now.cur;return 0;}for (int i = 0; i < 8; i++){int nextx = now.x + mov[i][0], nexty = now.y + mov[i][1];if (!over(nextx, nexty)&&!vis[nextx][nexty]){point newp = {now.cur+1, nextx, nexty};vis[nextx][nexty] = 1;q.push(newp);}}}
}int main()
{//freopen("E://in.txt", "r", stdin);char s1, s2, mid;while(scanf("%c%d%c%c%d", &s1, &sy, &mid, &s2, &ey) != EOF){getchar();sy -= 1;ey -= 1;sx = s1 - 'a';ex = s2 - 'a';bfs();printf("To get from %c%d to %c%d takes %d knight moves.\n",s1, sy+1, s2, ey+1, ans);memset(vis, 0, sizeof(vis));ans = 0;}return 0;
}