笔记本做网站在线网页制作工具
1.BFS模板
//BFS模板
void BFS(int s){
queue<int> q;//定义队列
q.push(s);//起始结点入队
while(!q.empty()){//非空循环
取出队首元素top;
访问队首元素top;
队首元素出队;
将top的下一层结点中未曾入队的结点全部入队，并设置为以入队;
}
}
引例：求矩阵中相邻1块的个数（就是八连块个数 上下左右相邻才算一块）
例如下面第一1块的个数为4
先贴出测试数据
6 7 0 1 1 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 1 1 1 0 1 0 0 1 1 1 1 0 0 06 7 0 1 1 1 0 0 1 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 0 1 1 1 1 1 1 1 0 1 0 0 1 1 1 1 0 0 06 7 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 15 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 03 2 1 0 0 1 1 05 6 1 1 0 1 1 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 1 0 1 1 1 125 25 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 1 1 1 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1
上节的DFS实现，（简单一点）
#include<iostream> using namespace std;const int N=30; int n,m; int a[N][N]; // bool visited[N][N]={0};//开始都为false 没用到 直接赋值为2即可 省略可这一步 否则每次都要初始化 int num;void dfs(int i,int j){if(i<0||j<0||i>=n||j>=m) return;if(a[i][j]!=1) return;//1行不等于即可 都是后置判断 不会忽略第一个什么的a[i][j]=2;dfs(i,j+1);dfs(i,j-1);dfs(i+1,j);dfs(i-1,j); }void print(int a[N][N]){for(int i=0;i<n;i++){for(int j=0;j<m;j++){cout<<a[i][j]<<" ";}cout<<endl;}cout<<endl; }int main(){freopen("lx1dfs.txt","r",stdin);while(cin>>n>>m){for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>a[i][j];}}num=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(a[i][j]==1){num++;dfs(i,j);}}}cout<<num<<endl;//输出处理后的数组// print(a);}return 0; }
bfs实现：（自己实现，改了个大bug，关于inqueue的含义）
原始代码：
#include<iostream> #include <algorithm> #include <cstring> #include <queue> #include<ctime> using namespace std;const int N=100; int n,m,matrix[N][N],num; // bool inque[N][N]={false}; //还是不要 直接将值置为2 int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0};struct Node{int x,y;Node(){}Node(int x,int y){this->x=x;this->y=y;} };void print(int a[N][N]){for(int i=0;i<n;i++){for(int j=0;j<m;j++){cout<<a[i][j]<<" ";}cout<<endl;}cout<<endl; }bool judge(Node node){if(node.x<0||node.x>=n||node.y<0||node.y>=m) return false;if(matrix[node.x][node.y]!=1) return false;return true; }//没有递归 只有循环 void bfs(Node node){queue<Node> q;q.push(node);matrix[node.x][node.y]=2;//入队了time_t start ,end;double cost;time(&start);while(!q.empty()){Node top=q.front();q.pop();//严重错误 改正后加了两行43 56//正确做法 每次入队一个置一个2 或者bool数组置为true//不可以在此处写matrix[top.x][top.y]=2; 然后其他地方不写 //因为入队元素太多，有些尚未来得及pop()，又没有做标记，可能导致循环push//也即是push后没有立马置为2 可能导致多次push 最终可能陷入死循环//正确操作，每push一次 置一次2for(int i=0;i<4;i++){Node nextno=Node(top.x+dx[i],top.y+dy[i]);if(judge(nextno)){q.push(nextno);matrix[nextno.x][nextno.y]=2;//入队了}}time(&end);cost=difftime(end,start);if(cost>=2){print(matrix);time(&start);}} }int main(){freopen("input1.txt","r",stdin);while(cin>>n>>m){for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>matrix[i][j];}}num=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(matrix[i][j]==1){num++;Node node=Node(i,j);bfs(node);}}}cout<<num<<endl;print(matrix);}return 0; }原始代码运行结果：
4 0 2 2 2 0 0 2 0 0 2 0 0 0 0 0 0 0 0 2 0 0 0 0 0 2 2 2 0 2 2 2 0 2 0 0 2 2 2 2 0 0 05 0 2 2 2 0 0 2 0 0 2 0 0 0 0 2 2 0 0 2 0 0 0 0 0 2 2 2 2 2 2 2 0 2 0 0 2 2 2 2 0 0 01 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 03 2 0 0 2 2 07 2 2 0 2 2 2 2 0 2 0 2 0 2 0 0 2 0 2 0 2 2 0 2 0 2 0 2 2 2 215 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 2 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 2 2 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 2 2 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 2 2 0 2 2 2 2 2 2 0 0 2 2 2 2 2 2 2 2 2 2 2 2 0 2 2 2 0 2 2 2 2 2 0 2 0 2 2 2 2 2 2 2 2 2 2 2 2 0 2 2 2 0 2 2 2 2 0 2 0 0 2 2 2 2 2 2 2 2 2 2 2 2 0 0 2 0 2 2 2 2 0 2 0 2 0 2 2 2 2 2 2 2 2 2 2 2 2 2 0 0 2 2 2 2 0 2 0 2 2 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 2 0 2 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 2 0 2 2 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 2 2 2 2 2 2 2 0 0 0 0 0 2 2 2 2 2 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 0 2 2 0 2 2 2 2 2 0 2 2 2 0 2 2 2 2 2 2 2 2 2 2 2 0 2 0 2 2 2 2 2 0 0 0 0 0 0 0 0 2 2 2 2 2 2 2 2 2 0 0 2 2 2 2 2 2 2 0 0 2 0 0 2 2 2 2 2 2 2 2 2 2 2 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 2 0 2 2 2 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 2 0 2 2 2 0 2 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 2请按任意键继续. . .
化简后的代码：
#include<iostream> #include <cstring> #include <queue> using namespace std;const int N=100; int n,m,matrix[N][N],num; // bool inque[N][N]={false}; //还是不要 直接将值置为2 int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0};struct Node{int x,y;Node(){}Node(int x,int y){this->x=x;this->y=y;} };bool judge(Node node){if(node.x<0||node.x>=n||node.y<0||node.y>=m) return false;if(matrix[node.x][node.y]!=1) return false;return true; }//没有递归 只有循环 void bfs(Node node){queue<Node> q;q.push(node);matrix[node.x][node.y]=2;//入队了while(!q.empty()){Node top=q.front();q.pop();//严重错误 改正后加了两行43 56//正确做法 每次入队一个置一个2 或者bool数组置为true//不可以在此处写matrix[top.x][top.y]=2; 然后其他地方不写 //因为入队元素太多，有些尚未来得及pop()，又没有做标记，可能导致循环push//也即是push后没有立马置为2 可能导致多次push 最终可能陷入死循环//正确操作，每push一次 置一次2for(int i=0;i<4;i++){Node nextno=Node(top.x+dx[i],top.y+dy[i]);if(judge(nextno)){q.push(nextno);matrix[nextno.x][nextno.y]=2;//入队了}}} }int main(){freopen("input1.txt","r",stdin);while(cin>>n>>m){for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>matrix[i][j];}}num=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(matrix[i][j]==1){num++;Node node=Node(i,j);bfs(node);}}}cout<<num<<endl;// print(matrix);}return 0; }化简后代码运行结果：
书上的代码：
#include <cstdio> #include <queue> #include <algorithm> using namespace std; const int maxn=100; struct node {int x,y; }Node;int n,m; int matrix[maxn][maxn]; bool inq[maxn][maxn]={false}; int X[4]={0,0,1,-1}; int Y[4]={1,-1,0,0};bool judge(int x,int y){if(x>=n||x<0||y>=m||y<0) return false;if(matrix[x][y]==0||inq[x][y]==true) return false;return true; }void BFS(int x,int y){queue<node> Q;Node.x=x,Node.y=y;Q.push(Node);inq[x][y]=true;while(!Q.empty()){node top=Q.front();Q.pop();for(int i=0;i<4;i++){int newX=top.x+X[i];int newY=top.y+Y[i];if(judge(newX,newY)){Node.x=newX,Node.y=newY;Q.push(Node);inq[newX][newY]=true;}}} }int main(){freopen("input1.txt","r",stdin);while(scanf("%d%d",&n,&m)!=EOF){for(int x=0;x<n;x++){for(int y=0;y<m;y++){scanf("%d",&matrix[x][y]);}}int ans=0;fill(inq[0],inq[0]+maxn*maxn,false);for(int x=0;x<n;x++){for(int y=0;y<m;y++){if(matrix[x][y]==1&&inq[x][y]==false){ans++;BFS(x,y);}}}printf("%d\n", ans);}return 0; }
特别强调：在BFS中设置的inque数组的含义是判断结点是否已入过队，而不是结点是否已被访问。区别在于：如果设置成是否已被访问，有可能在某个结点正在队列中（但还未访问）时由于其他结点可以到达它而将这个结点再次入队，导致很多结点反复入队，计算量大大增加。甚至可能发生死循环。因此BFS中让每个结点只入队一次，故需要设置inque数组的含义为结点是否已入队而非结点是否被访问过。
bug版本如下： 最后一组测试数据有bug
#include<iostream> #include <algorithm> #include <cstring> #include <queue> #include<ctime> using namespace std;const int N=100; int n,m,matrix[N][N],num; // bool inque[N][N]={false}; //还是不要 直接将值置为2 int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0};struct Node{int x,y;Node(){}Node(int x,int y){this->x=x;this->y=y;} };void print(int a[N][N]){for(int i=0;i<n;i++){for(int j=0;j<m;j++){cout<<a[i][j]<<" ";}cout<<endl;}cout<<endl; }bool judge(Node node){if(node.x<0||node.x>=n||node.y<0||node.y>=m) return false;if(matrix[node.x][node.y]!=1) return false;return true; }//没有递归 只有循环 void bfs(Node node){queue<Node> q;q.push(node);//入队不设置标记time_t start ,end;double cost;time(&start);while(!q.empty()){Node top=q.front();q.pop();matrix[top.x][top.y]=2;//访问了for(int i=0;i<4;i++){Node nextno=Node(top.x+dx[i],top.y+dy[i]);if(judge(nextno)){q.push(nextno);//入队不设置标记}}time(&end);cost=difftime(end,start);if(cost>=2){print(matrix);time(&start);}} }int main(){freopen("input1.txt","r",stdin);while(cin>>n>>m){for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>matrix[i][j];}}num=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(matrix[i][j]==1){num++;Node node=Node(i,j);bfs(node);}}}cout<<num<<endl;print(matrix);}return 0; }运行结果：死循环
4 0 2 2 2 0 0 2 0 0 2 0 0 0 0 0 0 0 0 2 0 0 0 0 0 2 2 2 0 2 2 2 0 2 0 0 2 2 2 2 0 0 05 0 2 2 2 0 0 2 0 0 2 0 0 0 0 2 2 0 0 2 0 0 0 0 0 2 2 2 2 2 2 2 0 2 0 0 2 2 2 2 0 0 01 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 03 2 0 0 2 2 07 2 2 0 2 2 2 2 0 2 0 2 0 2 0 0 2 0 2 0 2 2 0 2 0 2 0 2 2 2 22 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 1 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 0 0 0 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 1 1 0 2 2 2 2 2 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 1 1 0 2 2 2 2 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 1 1 0 2 2 2 1 1 1 0 0 2 2 2 2 2 2 2 2 2 2 2 2 0 1 1 1 0 2 2 1 1 1 0 1 0 2 2 2 2 2 2 2 2 2 2 2 2 0 1 1 1 0 2 1 1 1 0 1 0 0 2 2 2 2 2 2 2 2 2 2 2 2 0 0 1 0 1 1 1 1 0 1 0 1 0 2 2 2 2 2 2 2 2 2 2 2 2 2 0 0 1 1 1 1 0 1 0 1 1 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 0 1 0 1 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 0 1 0 1 1 0 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 0 1 1 1 2 2 2 2 0 0 0 0 0 2 2 2 2 1 0 0 0 1 1 1 1 1 1 1 1 2 2 2 2 0 1 1 0 2 2 2 2 1 0 1 1 1 0 1 1 1 1 1 1 1 2 2 2 2 0 1 0 1 2 2 2 1 0 0 0 0 0 0 0 0 1 1 1 1 1 2 2 2 2 0 0 1 1 1 2 1 1 1 0 0 1 0 0 1 1 1 1 1 1 1 2 2 2 2 0 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 0 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 2 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 12 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 1 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 1 1 0 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 1 1 0 2 2 2 2 2 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 1 1 0 2 2 2 2 1 1 0 0 2 2 2 2 2 2 2 2 2 2 2 2 0 1 1 1 0 2 2 2 1 1 0 1 0 2 2 2 2 2 2 2 2 2 2 2 2 0 1 1 1 0 2 2 1 1 0 1 0 0 2 2 2 2 2 2 2 2 2 2 2 2 0 0 1 0 1 2 1 1 0 1 0 1 0 2 2 2 2 2 2 2 2 2 2 2 2 2 0 0 1 1 1 1 0 1 0 1 1 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 0 1 0 1 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 0 1 0 1 1 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 0 1 1 1 2 2 2 2 0 0 0 0 0 2 2 2 2 2 0 0 0 1 1 1 1 1 1 1 1 2 2 2 2 0 1 1 0 2 2 2 2 2 0 1 1 1 0 1 1 1 1 1 1 1 2 2 2 2 0 1 0 2 2 2 2 2 0 0 0 0 0 0 0 0 1 1 1 1 1 2 2 2 2 0 0 2 1 2 2 2 1 1 0 0 1 0 0 1 1 1 1 1 1 1 2 2 2 2 0 2 2 2 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 0 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 2 2 2 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 2 2 2 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1
2.起点到终点最短距离
给定一个n*m大小的迷宫，其中*代表不可通过的墙壁，而“.”代表平地，S代表起点，T代表终点。移动过程中，如果当前位置是（x,y）(下标从0开始）且每次只能前往上下左右（x,y+1）,(x,y-1),(x-1,y),(x+1,y)四个位置的平地，求从起点S到达终点T的最少步数
. . . . .
. * . * .
. * S * .
. * * * .
. . . T *
S(2,2) T(4,3)
解析：最短步数就是BFS访问到改结点的层数
#include<iostream>
#include <queue>
#include <algorithm>
using namespace std;const int N=30;
int n,m;
char a[N][N];
bool inque[N][N]={false};
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
struct Node
{int x,y;int step;Node(){step=0;}Node(int x,int y){this->x=x;this->y=y;step=0;}
}start,end;bool judge(Node node){if(node.x<0||node.x>=n||node.y<0||node.y>=m) return false;//不能写!='.' 因为S T也可以通过if(a[node.x][node.y]=='*'||inque[node.x][node.y]==true) return false;return true;
}void bfs(Node start){queue<Node> q;q.push(start);start.step=0;inque[start.x][start.y]=true;while(!q.empty()){Node top=q.front();q.pop();if(a[top.x][top.y]=='T'){//找到了 输出层数(最短步数) 直接returncout<<top.step<<endl;return;}for(int i=0;i<4;i++){Node next=Node(top.x+dx[i],top.y+dy[i]);if(judge(next)){next.step=top.step+1;//放到push后面赋值还不行 注意c/c++结构体名做参数入栈传递的是副本 不是地址q.push(next);inque[next.x][next.y]=true; }}}cout<<"无可达路径\n";
}int main(){freopen("input2.txt","r",stdin);while(cin>>n>>m){for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>a[i][j];if(a[i][j]=='S'||a[i][j]=='s'){start.x=i;start.y=j;}else if(a[i][j]=='T'||a[i][j]=='t'){end.x=i;end.y=j;}}}fill(inque[0],inque[0]+N*N,false);// cout<<"start:"<<start.x<<" "<<start.y<<endl;// cout<<"end:"<<end.x<<" "<<end.y<<endl;bfs(start);}return 0;
}测试数据与运行结果：
测试数据：
5 5
. . . . .
. * . * .
. * S * .
. * * * .
. . . T *5 6
. . . . . .
. * . * . .
. * S * . *
. * * * . *
. . . T . .25 25
. . . . * . . . . . . . . . . . . . . . . . . . .
. * * . . * . . . . . . . . . . . . . . . . . . .
. . . * . * . . . . . . . . . . . . . . . . . . .
. . . * . * * * * * * * * * * . . . . . . . . . .
. . . * . . . . . . . . . . * . . . . . . . . . .
. . . . * * * * * * . . . . * . . . . . . . . . .
. . . . . . . . . S * * * . . * . . . . . . . . .
. . . . . . . . . . * T * . . * . . . . . . . . .
. . . . . . . . . . * . . * . * . . . . . . . . .
. . . . . . . . . . * . . * . * . . . . . . . . .
. . . . . . . . . . * . . * . * . . . . . . . . .
. . . . . . . . . . * . . * . * . . . . . . . . .
. . . . . . . . . . * . . * . * . . . . . . . . .
. . . . . . . . . . * . * . . * . . . . . . . . .
. . . . . . . . . . * . * . * * . . . . . . . . .
. . . . . . . . . . * . * . * . . . . . . . . . .
. . . . . . . . . . * . * . * . . . . . . . . . .
. . . . . . . . . . * . * . * . . . . . . . . . .
. . . . . . . . . . * . * . * . . . . . . . . . .
. . . . . . . . . . * . * . * . . . . . . . . . .
. . . . . . . . . . * . * . * . . . . . . . . . .
. . . . . . . . . . * . * . * . . . . . . . . . .
. . . . . . . . . . * . * . * . . . . . . . . . .
. . . . . . . . . . * . * . * . . . . . . . . . .
. . . . . . . . . . * . . . . . . . . . . . . . . 运行结果：
11
9
73注意点2：当使用STL的queue时，元素入队的push操作只是制造了该元素的一个副本入队，因此在入队后对原元素的修改不会影响队列中的副本，而对队列中的副本的修改也不会改变原元素，需要注意由此可能引入的bug(一般由结构体产生）
例如上面例子44行若写在45行之后则会导致出错！
相关链接