dfs的递归实现。
dfs的栈实现。
bfs的队列实现：
对于队列的操作：
入队，如例：q.push(x); 将x 接到队列的末端。
出队，如例：q.pop(); 弹出队列的第一个元素，注意，并不会返回被弹出元素的值。
访问队首元素，如例：q.front()，即最早被压入队列的元素。
访问队尾元素，如例：q.back()，即最后被压入队列的元素。
判断队列空，如例：q.empty()，当队列空时，返回true。
A - Knight Moves
Background
Mr Somurolov, fabulous chess-gamer indeed, asserts that no one else but him can move knights from one position to another so fast. Can you beat him?
The Problem
Your task is to write a program to calculate the minimum number of moves needed for a knight to reach one point from another, so that you have the chance to be faster than Somurolov.
For people not familiar with chess, the possible knight moves are shown in Figure 1.
Input
The input begins with the number n of scenarios on a single line by itself.
Next follow n scenarios. Each scenario consists of three lines containing integer numbers. The first line specifies the length l of a side of the chess board (4 <= l <= 300). The entire board has size l * l. The second and third line contain pair of integers {0, ..., l-1}*{0, ..., l-1} specifying the starting and ending position of the knight on the board. The integers are separated by a single blank. You can assume that the positions are valid positions on the chess board of that scenario. Output For each scenario of the input you have to calculate the minimal amount of knight moves which are necessary to move from the starting point to the ending point. If starting point and ending point are equal,distance is zero. The distance must be written on a single line. Sample Input
Mr Somurolov, fabulous chess-gamer indeed, asserts that no one else but him can move knights from one position to another so fast. Can you beat him?
The Problem
Your task is to write a program to calculate the minimum number of moves needed for a knight to reach one point from another, so that you have the chance to be faster than Somurolov.
For people not familiar with chess, the possible knight moves are shown in Figure 1.
Next follow n scenarios. Each scenario consists of three lines containing integer numbers. The first line specifies the length l of a side of the chess board (4 <= l <= 300). The entire board has size l * l. The second and third line contain pair of integers {0, ..., l-1}*{0, ..., l-1} specifying the starting and ending position of the knight on the board. The integers are separated by a single blank. You can assume that the positions are valid positions on the chess board of that scenario. Output For each scenario of the input you have to calculate the minimal amount of knight moves which are necessary to move from the starting point to the ending point. If starting point and ending point are equal,distance is zero. The distance must be written on a single line. Sample Input
3 8 0 0 7 0 100 0 0 30 50 10 1 1 1 1Sample Output
5 28 0
代码：
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <queue> #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; const int maxn=300+5; int vis[maxn][maxn]; int n; int dx[]={-2,-1,1,2,2,1,-1,-2}; int dy[]={1,2,2,1,-1,-2,-2,-1}; struct Node { int x,y,step; }; queue<Node> Q; bool check(int x,int y) { if(x<0||x>=n||y<0||y>=n) return false; if(vis[x][y]) return false; return true; } int BFS(int x1,int y1,int x2,int y2) { while(!Q.empty()) Q.pop(); vis[x1][y1]=1; Q.push((Node){x1,y1,0}); while(!Q.empty()) { Node u = Q.front(); Q.pop(); if(u.x == x2 && u.y == y2) return u.step; for(int i = 0; i < 8; i ++){ int x=u.x+dx[i]; int y=u.y+dy[i]; if(check(x,y)){ vis[x][y]=1; Q.push(Node{x,y,u.step+1}); } } } return 0; } int main() { int T; scanf("%d",&T); while(T--) { int x1,y1,x2,y2; scanf("%d%d%d%d%d",&n,&x1,&y1,&x2,&y2); mem(vis,0); int ans=BFS(x1,y1,x2,y2); printf("%d\n",ans); } return 0; }
代码解析：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue> c++的队列要调用的头文件
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int maxn=300+5;
int vis[maxn][maxn]; 定义地图用1和0表示走没走过
int n; 地图尺寸
int dx[]={-2,-1,1,2,2,1,-1,-2};
int dy[]={1,2,2,1,-1,-2,-2,-1}; 移动方向数组
struct Node 定义结构体用于存放x，y坐标和步数。最后放进队列中
{
int x,y,step;
};
queue<Node> Q; 定义node（前面定义的结构体名）型的队列Q
bool check(int x,int y) 用于检测这个点是不是可以走（边界检测和检测vis是不是1）
{
if(x<0||x>=n||y<0||y>=n)
return false;
if(vis[x][y])
return false;
return true;
}
int BFS(int x1,int y1,int x2,int y2) bfs核心函数
{
while(!Q.empty()) 清空队列
Q.pop();
vis[x1][y1]=1; 将起点置1
Q.push((Node){x1,y1,0}); 把起点压入队列
while(!Q.empty()) 如果队列不空
{
Node u = Q.front(); 定义结构体u存放队头数据
Q.pop(); 清空队头
if(u.x == x2 && u.y == y2)
return u.step; 判断输出结果
for(int i = 0; i < 8; i ++){ 8种移动情况
int x=u.x+dx[i];
int y=u.y+dy[i];
if(check(x,y)){ 检测可不可以走
vis[x][y]=1; 地图上置1
Q.push(Node{x,y,u.step+1}); 把每一步压入队列
}
}
}
return 0;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int x1,y1,x2,y2;
scanf("%d%d%d%d%d",&n,&x1,&y1,&x2,&y2);
mem(vis,0);
int ans=BFS(x1,y1,x2,y2);
printf("%d\n",ans);
}
return 0;
}
其实主要思想是把改点的下一步涉及到的点压入队列，然后在队头删除这个点，如此重复，最后找到要找的点。