训练第二周之BFS例题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
using namespace std;
struct position
{
int x,y;//x坐标，y坐标
};
typedef struct position Node;
bool visit[6][6]={0};//判断是否为白色节点
int state[6][6];//输入迷宫状态
Node ans[25][25];//记录所到节点*前一步*的坐标
bool isValid(Node vw)//判断该位置是否合法
{
if(vw.x<0||vw.x>4||vw.y<0||vw.y>4)//是否在迷宫内
return false;
if(state[vw.x][vw.y]==1)//是否是墙壁
return false;
return true;
}
bool bfs(Node vs,Node vd)//宽度优先搜索
{
queue<Node> q;//建立队列
Node vn,vw;
int move[4][4]={{-1,0},{1,0},{0,-1},{0,1}};//有四种移动
memset(visit,false,sizeof(visit));
q.push(vs);//将起点加入队列
visit[vs.x][vs.y]=1;//将起点变成灰色
while(!q.empty())
{
vn=q.front();//将队列头抽出
q.pop();//将该节点变黑(踢出队列)
for(int i=0;i<4;i++)
{
vw.x=vn.x+move[i][0];
vw.y=vn.y+move[i][1];
if(vw.x==vd.x&&vw.y==vd.y)
{
ans[vw.x][vw.y]=vn;//将前一步的坐标赋给ans[vw.x][vw.y]
return true;
}
if(isValid(vw)&&!visit[vw.x][vw.y])
{
q.push(vw);//加入队列
ans[vw.x][vw.y]=vn;//记录前一步
visit[vw.x][vw.y]=1;//将该节点变灰
//printf("%d %d %dn",vw.x,vw.y,vw.sum);
}
}
}
return false;
}
void road(Node vd)//输出路径
{
stack<Node> s;//建立栈
Node vw;
vw.x=vd.x;
vw.y=vd.y;
while(vw.x!=0||vw.y!=0)//不到达起点就一直放
{
s.push(vw);//加入栈
vw=ans[vw.x][vw.y];//把前一步的坐标赋给该节点
}
printf("(0, 0)n");
while(!s.empty())
{
vw=s.top();//抽栈头
s.pop();//移除该节点
printf("(%d, %d)n",vw.x,vw.y);
}
return;
}
int main(){
int i,j;
Node vs,vd;
for(i=0;i<5;i++)
for(j=0;j<5;j++)
scanf("%d",&state[i][j]);
vs.x=0;
vs.y=0;
vd.x=4;
vd.y=4;
bfs(vs,vd);
road(vd);
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
char state[25][25];
bool visit[25][25];
int sum=1;//记录所走的黑瓷砖总数
int w,h;
struct Node
{
int x,y;
};
bool isValid(Node vw,int w,int h)//判断vw是否合法
{
if(vw.x<0||vw.x>=h||vw.y<0||vw.y>=w)
return false;
if(state[vw.x][vw.y]!='.')
return false;
return true;
}
void bfs(Node vs,int w,int h)
{
queue<Node> q;
memset(visit,false,sizeof(visit));
Node vw,vn;
int move[4][4]={{-1,0},{1,0},{0,-1},{0,1}};
q.push(vs);
visit[vs.x][vs.y]=1;
while(!q.empty())//一步步过去直到队列为空
{
vn=q.front();
q.pop();
for(int i=0;i<4;i++)
{
vw.x=vn.x+move[i][0];
vw.y=vn.y+move[i][1];
//printf("%d %d %d %dn",vw.x,vw.y,w,h);
if(isValid(vw,w,h)&&!visit[vw.x][vw.y])
{
sum+=1;
q.push(vw);
visit[vw.x][vw.y]=1;
}
}
}
return;
}
int main()
{
int i,j;
Node vs;
while(scanf("%d%d",&w,&h)!=EOF&&w&&h)
{
sum=1;
memset(state,0,sizeof(state));
for(i=0;i<h;i++)
scanf("%s",state[i]);
for(i=0;i<h;i++)//找到起点
for(j=0;j<w;j++)
if(state[i][j]=='@')
{
vs.x=i;
vs.y=j;
}
bfs(vs,w,h);
printf("%dn",sum);
}
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int ans[305][305];//记录 knight moves
bool visit[305][305];//标记为灰色节点
int Move[8][8]={{-2,1},{-1,2},{1,2},{2,1},
{2,-1},{1,-2},{-1,-2},{-2,-1}};//八种移动。这里move小写就CE了，不懂。。。
struct node
{
int x,y;
};
bool isValid(node vw,int l)
{
if(vw.x<0||vw.x>=l||vw.y<0||vw.y>=l)
return false;
return true;
}
void bfs(node vs,node vd,int l)
{
queue<node> q;
node vn,vw;
memset(visit,false,sizeof(visit));
memset(ans,0,sizeof(ans));
q.push(vs);
visit[vs.x][vs.y]=1;
while(!q.empty())
{
vn=q.front();
q.pop();
for(int i=0;i<8;i++)
{
vw.x=vn.x+Move[i][0];
vw.y=vn.y+Move[i][1];
if(vw.x==vd.x&&vw.y==vd.y)//是否到达终点
{
ans[vd.x][vd.y]=ans[vn.x][vn.y]+1;
//printf("%dn",ans[vd.x][vd.y]);
return;
}
if(isValid(vw,l)&&!visit[vw.x][vw.y])//判断vw是否合法且为白色节点
{
ans[vw.x][vw.y]=ans[vn.x][vn.y]+1;
q.push(vw);
visit[vw.x][vw.y]=1;
//printf("%d %d %dn",vw.x,vw.y,ans[vw.x][vw.y]);
}
}
}
return;
}
int main()
{
int n,l,x1,y1,x2,y2;
node vs,vd;
scanf("%d",&n);
while(n--)
{
scanf("%d",&l);
scanf("%d%d",&x1,&y1);
scanf("%d%d",&x2,&y2);
vs.x=x1;
vs.y=y1;
vd.x=x2;
vd.y=y2;
//printf("%d %d %d %dn",vs.x,vs.y,vd.x,vd.y);
if(vs.x==vd.x&&vs.y==vd.y)//起点终点相同直接输出0
printf("0n");
else
{
bfs(vs,vd,l);
printf("%dn",ans[vd.x][vd.y]);
}
}
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<stdio.h>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<queue>
using namespace std;
#define way3(x) x*2
struct node
{
int x;
};
typedef struct node Node;
int sum[100005]={0};
bool visit[100005];
bool limit(int x)
{
if(x>=0&&x<=100000)
return true;
return false;
}
bool bfs(Node vs,Node vd)
{
Node vw,vn;
queue<Node> q;
int i;
memset(visit,false,sizeof(visit));
memset(sum,0,sizeof(sum));
q.push(vs);
visit[vs.x]=true;
int way[2]={-1,1};
while(!q.empty())
{
vn=q.front();
q.pop();
for(i=0;i<2;i++){
vw.x=vn.x+way[i];
if(vw.x==vd.x)
{
sum[vd.x]=sum[vn.x]+1;
return true;
}
if(limit(vw.x)&&!visit[vw.x])
{
q.push(vw);
visit[vw.x]=1;
sum[vw.x]=sum[vn.x]+1;
}
}
vw.x=way3(vn.x);
if(vw.x==vd.x)
{
sum[vd.x]=sum[vn.x]+1;
return true;
}
if(limit(vw.x)&&!visit[vw.x])
{
q.push(vw);
visit[vw.x]=1;
sum[vw.x]=sum[vn.x]+1;
}
}
return false;
}
int main(){
Node N,K;
while(scanf("%d%d",&N.x,&K.x)!=EOF){
//scanf("%d%d",&N.x,&K.x);
if(N.x>=K.x)//已经在牛的后面就不能再乘以2了只要相减
printf("%dn",N.x-K.x);
else{
bfs(N,K);
printf("%dn",sum[K.x]);
}
}
return 0;
}