建议加vis访问数组
模版一
题目描述
当你站在一个迷宫里的时候，往往会被错综复杂的道路弄得失去方向感，如果你能得到迷宫地图，事情就会变得非常简单。假设你已经得到了一个n*m的迷宫的图纸，请你找出从起点到出口的最短路。
输入
第一行是两个整数n和m(1<=nm<=100)，表示迷宫的行数和列数。接下来n行，每行一个长为m的字符串，表示整个迷宫的布局。字符'.'表示空地，'#'表示墙，'S'表示起点'T'表示出口。
输出
输出从起点到出口最少需要走的步数。
样例
输入
5 7
1 0 0 0 0 1 0
0 0 1 0 1 0 0
0 0 0 0 1 0 1
0 1 1 0 0 0 0
0 0 0 0 1 1 0
1 3 1 7
输出
6
代码
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
int n,m,sx,sy,ex,ey,d[4][2]={-1,0,0,1,1,0,0,-1};
char a[105][105];
struct node{
int x;
int y;
int step;
};
void bfs(int x,int y){
queue<node> q;
a[x][y]='#';
q.push((node){x,y,0});
while(!q.empty()){
for(int i=0;i<4;i++){
int dx=q.front().x+d[i][0];
int dy=q.front().y+d[i][1];
if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&a[dx][dy]!='#'){
a[dx][dy]='#';
q.push((node){dx,dy,q.front().step+1});
if(dx==ex&&dy==ey){
cout<<q.front().step+1;
return ;
}
}
}
q.pop();
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
if(a[i][j]=='S'){
sx=i;
sy=j;
}
if(a[i][j]=='T'){
ex=i;
ey=j;
}
}
}
bfs(sx,sy);
return 0;
}
模版二
题目描述
有n*m的迷宫，该迷宫有一个入口，一个出口。编写一程序打印一条从迷宫入口到出口的最短路径，黑色方块的单元表示走不通（用1表示），白色方块的内容表示走的通（用0表示）
只能往上下左右四个方向走，如果有最短路径，保证最短路径一定是唯一的，如果没有路径可以到达，则输出“no way”。
输入
第一行输入2个整数n和m(n和m都是10~150之间的整数)，代表迷宫的行数和列数
接下来n行，每行有m个整数，1代表不可走的点，0代表可走的点
接下来一行，有2个整数s1和s2代表入口的坐标
接下来一行，有2个整数e1和e2代表出口的坐标
本题数据上保证出发点和终点的值一定为0，也就是不存在出发点和终点不能走的情况
输出
输出从入口到出口的最短路径，如果没有路径可达输出“no way”
样例
输入
8 5
1 1 1 1 1
0 0 0 0 1
1 1 1 0 1
1 0 0 0 1
1 0 0 1 1
1 0 0 0 1
1 1 1 0 1
1 0 0 0 1
2 1
8 4
输出
(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)->(4,3)->(5,3)->(6,3)->(6,4)->(7,4)->(8,4)
代码
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
int n,m,a[155][155],sx,sy,ex,ey;
int d[4][2]={-1,0,0,1,1,0,0,-1};
int f[155][155][2];
struct node{
int x;
int y;
};
void print(int x,int y){
if(x==0&&y==0)return ;
print(f[x][y][0],f[x][y][1]);
cout<<"("<<x<<","<<y<<")"<<"->";
}
void bfs(int x,int y){
queue<node> q;
q.push((node){x,y});
a[x][y]=1;
f[x][y][0]=0;
f[x][y][1]=0;
while(!q.empty()){
for(int i=0;i<4;i++){
int dx=q.front().x+d[i][0],dy=q.front().y+d[i][1];
if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&a[dx][dy]!=1){
a[dx][dy]=1;
f[dx][dy][0]=q.front().x;
f[dx][dy][1]=q.front().y;
q.push((node){dx,dy});
if(dx==ex&&dy==ey){
print(f[dx][dy][0],f[dx][dy][1]);
cout<<"("<<dx<<","<<dy<<")";
return ;
}
}
}
q.pop();
}
cout<<"no way";
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)cin>>a[i][j];
}
cin>>sx>>sy>>ex>>ey;
bfs(sx,sy);
return 0;
}
模版三
题目描述
农夫约翰在农场工作了一天，感觉比较累，准备开车回家。约翰在比较累的时候，喜欢走直路，不喜欢拐弯，哪怕走少拐弯的路回家更远，约翰也想走直路（好任性的约翰!）。请你从约翰的出发地到目的地找一条路，使得约翰回家拐弯数量最少。
输入
第一行两个整数n和m（n和m都是1000以内的整数），代表地图的大小。
接下来的n行，每行有m个数，其中能够同行的点用0表示，不能通行的点用1表示。
再接下来1行，有4个整数，s1、s2、e1、e2，s1和s2表示出发点的坐标，e1和e2表示目的地的坐标。（本题测试数据保证起点和终点不是同一个点，且起点和终点一定可以走）
输出
约翰从出发点到目的地最少要拐弯的数量，本题所有数据都确认从出发点到目的地是有路径可达的。
样例
输入
5 7
1 0 0 0 0 1 0
0 0 1 0 1 0 0
0 0 0 0 1 0 1
0 1 1 0 0 0 0
0 0 0 0 1 1 0
1 3 1 7
输出
5
代码
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
int n,m,sx,sy,ex,ey,d[4][2]={-1,0,0,1,1,0,0,-1};
int a[1005][1005],f[1005][1005];
struct node{
int x;
int y;
};
void bfs(int x,int y){
memset(f,0x7f,sizeof(f));
queue<node> q;
f[x][y]=-1;
q.push((node){x,y});
while(!q.empty()){
for(int i=0;i<4;i++){
int dx=q.front().x+d[i][0];
int dy=q.front().y+d[i][1];
while(dx>=1&&dx<=n&&dy>=1&&dy<=m&&a[dx][dy]==0){
if(f[q.front().x][q.front().y]+1<f[dx][dy]){
f[dx][dy]=f[q.front().x][q.front().y]+1;
q.push((node){dx,dy});
if(dx==ex&&dy==ey){
cout<<f[dx][dy];
return ;
}
}
dx+=d[i][0];
dy+=d[i][1];
}
}
q.pop();
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
cin>>sx>>sy>>ex>>ey;
bfs(sx,sy);
return 0;
}