kuangbin带你飞：
棋盘问题
![1]( "1")
简单的dfs，将row作为参数传入dfs，循环遍历column，注意dfs列之后要返回原先状态；
代码：
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
| #include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int vis[10];
char map[10][10];
int n,k,num,cnt;
void dfs(int r)
{
if(k==num)
{
cnt++;
return;
}
if(r>=n)
{
return;
}
for(int j=0;j<n;j++)
{
if(!vis[j]&&map[r][j]=='#')
{
vis[j]=1;
num++;
dfs(r+1);
vis[j]=0;
num--;
}
}
dfs(r+1);
}
int main()
{
while(cin>>n>>k)
{
if(n==-1&&k==-1)
{
break;
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>map[i][j];
}
}
memset(vis,0,sizeof(vis));
cnt=0;
num=0;
dfs(0);
cout<<cnt<<endl;
}
return 0;
}
|
Dungeon Master
![2.1]( "2.1")
![2.2PNG]( "2.2PNG")
迷宫问题拓展为三维状态，与普通的迷宫方法相同，只是使用三维数组表示状态，
代码：
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
| #include<iostream>
#include<string.h>
#include<queue>
#include<algorithm>
#include<math.h>
using namespace std;
int gx,gy,gz;
int bx,by,bz;
int l,r,c;
int res=0;
char map[31][31][31];
int vis[31][31][31];
int dir[6][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
struct node{
int x;
int y;
int z;
int step;
};
queue <node> q;
void bfs()
{
while(!q.empty())
{
node m=q.front();
q.pop();
if(m.x==gx&&m.y==gy&&m.z==gz)
{
cout<<"Escaped in "<<m.step<<" minute(s)."<<endl;
return ;
}
for(int i=0;i<6;i++)
{
int tmpx=m.x+dir[i][0];
int tmpy=m.y+dir[i][1];
int tmpz=m.z+dir[i][2];
if(!vis[tmpx][tmpy][tmpz]&&(map[tmpx][tmpy][tmpz]=='.'||map[tmpx][tmpy][tmpz]=='E')&&tmpx<l&&tmpx>=0&&tmpy<r&&tmpy>=0&&tmpz<c&&tmpz>=0)
{
vis[tmpx][tmpy][tmpz]=1;
node b;
b.x=tmpx;
b.y=tmpy;
b.z=tmpz;
b.step=m.step+1;
q.push(b);
}
}
}
cout<<"Trapped!"<<endl;
return;
}
int main()
{
while(cin>>l>>r>>c)
{
if(l==0&&r==0&&c==0)
{
break;
}
for(int i=0;i<l;i++)
{
for(int j=0;j<r;j++)
{
for(int k=0;k<c;k++)
{
cin>>map[i][j][k];
if(map[i][j][k]=='S')
{
bx=i;
by=j;
bz=k;
}
if(map[i][j][k]=='E')
{
gx=i;
gy=j;
gz=k;
}
}
}
}
node a;
a.x=bx;
a.y=by;
a.z=bz;
memset(vis,0,sizeof(vis));
vis[bx][by][bz]=1;
a.step=0;
while(!q.empty())
{
q.pop();
}
q.push(a);
bfs();
}
}
|
Catch That Cow
![3]( "3")
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
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=100001;
int vis[maxn],step[maxn];
queue<int>que;
int bfs(int N,int K)
{
int next,top;
que.push(N);
vis[N]=true;
step[N]=0;
while(!que.empty()){
top=que.front();
que.pop();
for(int i=0;i<3;i++){
if(i==0) next=top-1;
else if(i==1) next=top+1;
else next=top*2;
if(next<0||next>=maxn) continue;
if(!vis[next]){
que.push(next);
step[next]=step[top]+1;
vis[next]=true;
}
if(next==K) return step[next];
}
}
}
int main()
{
int N,K;
while(~scanf("%d%d",&N,&K)){
memset(step,0,sizeof(step));
memset(vis,false,sizeof(vis));
while(!que.empty()) que.pop();
if(N>=K) printf("%d\n",N-K);
else printf("%d\n",bfs(N,K));
}
return 0;
}
|
Fliptile
![4.1]( "4.1")
![4.2]( "4.2")
此题使用了二进制枚举法，题目的意思是有n*m个方格1是黑，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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
| #include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
const int N=16;
int g[N][N];
int t[N][N];
int f[N][N];
int cnt;
int n,m;
int dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};
void flip(int x,int y)
{
++cnt;
f[x][y]=1;
t[x][y]^=1;
for(int i=0;i<4;i++)
{
int tmpx=x+dir[i][0];
int tmpy=y+dir[i][1];
if(tmpx>=0&&tmpx<n&&tmpy>=0&&tmpy<m)
{
t[tmpx][tmpy]^=1;
}
}
}
bool judge(int k)
{
cnt=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
t[i][j]=g[i][j];
}
}
for(int i=0;i<m;i++)
{
if(k&(1<<(m-1-i)))
{
flip(0,i);
}
}
for(int i=1;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(t[i-1][j]==1)
{
flip(i,j);
}
}
}
for(int j=0;j<m;j++)
{
if(t[n-1][j]!=0)
{
return false;
}
}
return true;
}
int main()
{
while(cin>>n>>m)
{
int tmp=-1;
int ans=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>g[i][j];
}
}
ans=m*n+1;
for(int i=0;i<(1<<m);i++)
{
if(judge(i)&&cnt<ans)
{
ans=cnt;
tmp=i;
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
f[i][j]=0;
}
}
if(tmp>=0)
{
judge(tmp);
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(j<m-1)
cout<<f[i][j]<<" ";
else
cout<<f[i][j]<<endl;
}
}
}
else
{
cout<<"IMPOSSIBLE"<<endl;
}
}
}
|
Find The Multiple
![5.1]( "5.1")
![alt]( "alt")
题目意思是输入一个数，输出的数是由1和0组成的输入的数的倍数，既可以用bfs也可以用dfs
bfs：最初队列里为1，bfs过程：取出后判断是否为倍数，然后enqueue（i*10）和enqueue（i*10+1）;
代码：
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
| #include<iostream>
#include<queue>
using namespace std;
typedef long long ll;
queue<ll>q;
ll ans=0;
ll s;
void bfs(ll i)
{
q.push(i);
while(!q.empty())
{
ll tmp=q.front();
q.pop();
if(tmp%s==0)
{
cout<<tmp<<endl;
break;
}
q.push(tmp*10);
q.push(tmp*10+1);
}
return;
}
int main()
{
while(cin>>s)
{
if(s==0)
{
break;
}
ans=0;
while(!q.empty())
{
q.pop();
}
bfs(1);
}
}
|
Prime Path
![6.1]( "6.1")
![6.2]( "6.2")
题目大意：给两个素数，要求将前一个素数一次改变一位数，改变到另外一个素数，且要求改变过程中的每一个数都是素数。此题先使用筛法求出0到9999之间的素数打标，然后bfs，循环每一位数，判断生成的数是否为目的值，注意判重原则为vis[num],即构成的四位数：
代码：
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
91
92
93
94
95
96
97
98
99
100
| #include<iostream>
#include<string.h>
#include<math.h>
#include<queue>
using namespace std;
struct node{
int x;
int step;
};
bool flag=false;
int prim[100001]={0};
int vis[100001]={0};
queue<node>q;
void prim_c()
{
memset(prim,0,sizeof(prim));
prim[1]=1;
for(int i=2;i<=9999;i++)
{
if(prim[i]!=1)
{
for(int j=2*i;j<=9999;j+=i)
{
prim[j]=1;
}
}
}
}
void bfs(int a,int b)
{
while(!q.empty())
{
q.pop();
}
node N;
N.x=a;
N.step=0;
q.push(N);
while(!q.empty())
{
node tmp;
tmp=q.front();
q.pop();
int tmpx=tmp.x;
int tmps=tmp.step;
if(tmpx==b)
{
flag=true;
cout<<tmps<<endl;
break;
}
int t[4];
int num=0;
t[0]=tmpx/1000;
t[1]=tmpx/100%10;
t[2]=tmpx/10%10;
t[3]=tmpx%10;
for(int i=0;i<4;i++)
{
int temp=t[i];
for(int j=0;j<10;j++)
{
if(t[i]!=j)
{
t[i]=j;
num=t[0]*1000+t[1]*100+t[2]*10+t[3];
}
if(prim[num]==0&&!vis[num]&&num>=1000&&num<=9999)
{
node insert;
insert.step=tmp.step+1;
insert.x=num;
q.push(insert);
vis[num]=1;
}
}
t[i]=temp;
}
}
}
int main()
{
int t;
cin>>t;
int tmp1,tmp2,ans;
prim_c();
while(t--)
{
cin>>tmp1>>tmp2;
ans=0;
memset(vis,0,sizeof(vis));
bfs(tmp1,tmp2);
if(!flag)
{
cout<<"Impossible"<<endl;
}
}
}
|
G- Shuffle’m Up
![7.1]( "7.1")
![alt photo]( "alt photo")
此题是一道模拟题，是洗牌过程，，将s1,s2交叉组成s12,然后从中间对半分，再次进行交叉，循环执行上述操作，问经过多少次操作后能够达到最终状态。此题使用两个数组进行模拟，然后使用set<string> .find来判重，如果有重复会形成无限循环输出impossible，需要注意多组输入每次对字符串的清空问题。
代码：
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
| #include<iostream>
#include<math.h>
#include<algorithm>
#include<set>
#define maxn 100001
using namespace std;
typedef long long ll;
string a,b,c,res;
set<string> m;
int main()
{
int cases;
cin>>cases;
int tmp=cases;
while(cases--)
{
int times=0;
int num;
cin>>num;
cin>>a;
cin>>b;
cin>>res;
int k=0;
while(1){
for(int i=0;i<num;i++)
{
c+=b[i];
c+=a[i];
}
int tmp0=m.size();
m.insert(c);
int tmp1=m.size();
times+=1;
if(res==c)
{
cout<<tmp-cases<<" "<<times<<endl;
times=0;
m.clear();
c.clear();
break;
}
if(tmp0==tmp1)
{
times=0;
cout<<tmp-cases<<" -1"<<endl;
m.clear();
c.clear();
break;
}
for(int i=0;i<num;i++)
{
a[i]=c[i];
}
for(int i=num;i<2*num;i++)
{
b[i-num]=c[i];
}
c="";
}
}
}
|
H- Pots
![8.1]( "8.1")
![8.2]( "8.2")
![8.2]( "8.2")
bfs打印路径问题，在结构体中加入一个string act用以记录路径方向：
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
| #include<iostream>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
const int MAX=110;
int A,B,C;
int vis[MAX][MAX];
string num[6]={"FILL(1)","DROP(1)","POUR(1,2)","FILL(2)","DROP(2)","POUR(2,1)"};
struct node{
int x;
int y;
string act;
int step;
};
queue<node>q;
bool flag=false;
void bfs(int A,int B)
{
vis[0][0]=1;
node a;
a.x=0;
a.y=0;
a.act="";
a.step=0;
q.push(a);
while(!q.empty())
{
node tmp=q.front();
q.pop();
int tmpx=tmp.x;
int tmpy=tmp.y;
string tmpa=tmp.act;
int tmps=tmp.step;
if(tmpx==C||tmpy==C)
{
flag=true;
cout<<tmps<<endl;
for(int i=0;i<tmp.act.length();i++)
{
int I=(tmp.act[i]-'1'+1);
cout<<num[I]<<endl;
}
break;
}
node in;
for(int i=0;i<6;i++)
{
in=tmp;
int tx,ty,ts;
string ta;
if(i==0)
{
in.x=A;
in.step+=1;
in.act+="0";
}
if(i==1)
{
in.x=0;
in.step+=1;
in.act+="1";
}
if(i==2)
{
if(tmpx>=B-tmpy)
{
in.x-=(B-in.y);
in.y=B;
in.act+="2";
in.step+=1;
}
else if(tmpx<B-tmpy)
{
in.y+=in.x;
in.x=0;
in.act+="2";
in.step+=1;
}
}
if(i==3)
{
in.y=B;
in.step+=1;
in.act+="3";
}
if(i==4)
{
in.y=0;
in.step+=1;
in.act+="4";
}
if(i==5)
{
if(tmpy>=A-tmpx)
{
in.y-=(A-in.x);
in.x=A;
in.step+=1;
in.act+="5";
}
else if(tmpy<A-tmpx)
{
in.x+=in.y;
in.y=0;
in.step+=1;
in.act+="5";
}
}
if(!vis[in.x][in.y])
{
vis[in.x][in.y]=1;
q.push(in);
}
}
}
if(!flag)
{
cout<<"impossible"<<endl;
}
}
int main()
{
cin>>A>>B>>C;
int ans=0;
flag=false;
memset(vis,0,sizeof(int)*MAX*MAX);
bfs(A,B);
}
|
J- Fire
![9]( "9")
两次bfs，第一次判断火烧到每个格子的最早时间，第二次bfs人的路径如果能够在火烧到之前走到相应的格子上就可以继续，否则continue,记录格子被火烧的时间初始值应设为-1，因为存在烧不到的情况，另外注意火可能不止一处。
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
|
#include<iostream>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXN=1005;
int ix,iy,gx,gy;
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
struct node{
int x;
int y;
int s;
};
queue<node>q;
bool flag=false;
int vis[MAXN][MAXN];
int vis1[MAXN][MAXN];
char map[MAXN][MAXN];
int ans=0;
int R,C;
void bfs_f()
{
node tmp;
while(!q.empty())
{
tmp=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int tmpx=tmp.x+dir[i][0];
int tmpy=tmp.y+dir[i][1];
int tmps=tmp.s+1;
if(vis[tmpx][tmpy]==-1&&map[tmpx][tmpy]!='#'&&tmpx<R&&tmpy<C&&tmpx>=0&&tmpy>=0)
{
node in;
in.x=tmpx;
in.y=tmpy;
in.s=tmps;
vis[tmpx][tmpy]=vis[tmp.x][tmp.y]+1;
q.push(in);
}
}
}
}
void bfs_p(int x,int y)
{
node tmp;
tmp.x=x;
tmp.y=y;
vis1[tmp.x][tmp.y]=1;
tmp.s=0;
q.push(tmp);
while(!q.empty())
{
tmp=q.front();
q.pop();
if(tmp.x==R-1||tmp.y==C-1||tmp.x==0||tmp.y==0)
{
flag=true;
ans=tmp.s+1;
break;
}
int tmpx;
int tmpy;
int tmps;
for(int i=0;i<4;i++)
{
tmpx=tmp.x+dir[i][0];
tmpy=tmp.y+dir[i][1];
tmps=tmp.s+1;
if(tmpx>=0&&tmpx<R&&tmpy<C&&tmpy>=0&&map[tmpx][tmpy]=='.'&&!vis1[tmpx][tmpy]&&(tmps<vis[tmpx][tmpy]||vis[tmpx][tmpy]==-1))
{
vis1[tmpx][tmpy]=1;
node in;
in.x=tmpx;
in.y=tmpy;
in.s=tmps;
q.push(in);
}
else
{
continue;
}
}
}
}
int main()
{
int cases;
cin>>cases;
while(cases--)
{
cin>>R>>C;
memset(vis,-1,sizeof(int)*MAXN*MAXN);
memset(vis1,0,sizeof(int)*MAXN*MAXN);
for(int i=0;i<R;i++)
{
for(int j=0;j<C;j++)
{
cin>>map[i][j];
if(map[i][j]=='J')
{
ix=i;
iy=j;
}
else if(map[i][j]=='F')
{
node tmp;
tmp.x=i;
tmp.y=j;
tmp.s=0;
vis[i][j]=0;
q.push(tmp);
}
}
}
ans=0;
bfs_f();
flag=false;
while(!q.empty())
{
q.pop();
}
bfs_p(ix,iy);
if(flag)
cout<<ans<<endl;
else
{
cout<<"IMPOSSIBLE"<<endl;
}
}
}
|
K-迷宫问题
![11]( "11")
![11.1]( "11.1")
![11.1]( "11.1")
同样的bfs求最短路，dfs打印输出路径：
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
|
#include<iostream>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
int map[5][5];
int vis[5][5];
int gx,gy;
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
bool flag=false;
struct node{
int x;
int y;
};
node father[5][5];
queue<node>q;
void dfs(int x,int y)
{
if(x==0&&y==0)
{
cout<<"(0, 0)"<<endl;
return;
}
dfs(father[x][y].x,father[x][y].y);
cout<<"("<<x<<","<<" "<<y<<")"<<endl;
}
void bfs()
{
while(!q.empty())
{
node tmp;
tmp=q.front();
q.pop();
if(tmp.x==4&&tmp.y==4)
{
dfs(tmp.x,tmp.y);
break;
}
int tmpx;
int tmpy;
for(int i=0;i<4;i++)
{
tmpx=tmp.x+dir[i][0];
tmpy=tmp.y+dir[i][1];
if(tmpx>=0&&tmpy>=0&&tmpx<5&&tmpy<5&&map[tmpx][tmpy]==0&&!vis[tmpx][tmpy])
{
vis[tmpx][tmpy]=1;
father[tmpx][tmpy].x=tmp.x;
father[tmpx][tmpy].y=tmp.y;
node in;
in.x=tmpx;
in.y=tmpy;
q.push(in);
}
}
}
}
int main()
{
for(int i=0;i<5;i++)
{
for(int j=0;j<5;j++)
{
cin>>map[i][j];
}
}
node a;
a.x=0;
a.y=0;
q.push(a);
memset(vis,0,sizeof(int)*25);
vis[0][0]=1;
bfs();
}
|
L -Oil Deposits
![12.1]( "12.1")
![12.2]( "12.2")
![12.2]( "12.2")
典型的dfs求连通分量，注意此题只是比一般的海岛问题多了一个维度而已，只要方向dir拓展为dir[8][2]即可。
代码：
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
| #include<iostream>
#include<string.h>
#include<algorithm>
#define MAXN 101
using namespace std;
int m,n;
int ans=0;
int dir[8][2]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}};
int vis[MAXN][MAXN];
char map[MAXN][MAXN];
void dfs(int x,int y)
{
map[x][y]='*';
for(int i=0;i<8;i++)
{
int tmpx=x+dir[i][0];
int tmpy=y+dir[i][1];
if(map[tmpx][tmpy]=='@')
{
dfs(tmpx,tmpy);
}
}
}
int main()
{
while(cin>>m>>n)
{
if(m==0&&n==0)
{
break;
}
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
cin>>map[i][j];
}
}
int ans=0;
memset(vis,0,sizeof(int)*MAXN*MAXN);
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(map[i][j]=='@')
{
ans++;
dfs(i,j);
}
}
}
cout<<ans<<endl;
}
return 0;
}
|
[M-非常可乐]（https://vjudge.net/contest/368000#problem/M）
![13.1]( "13.1")
![13.2PNG]( "13.2PNG")
也是bfs的实际应用，只要bfs每次列举3个杯子的不同操作即可，即A->B,A->C,B->A,C->A,B->C,C->B;即可，满足条件即可。
代码：
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define INF 0x7fffffff
using namespace std;
struct node{
int z;
int x;
int y;
int step;
};
node tmp,t;
int book[105][105][105];
int main()
{
int s,n,m;
while(cin>>s>>n>>m){
if(s==0&&n==0&&m==0)
{
break;
}
int flag=0;
if(s%2==1)
{
flag=0;
}
else
{
queue<node>q;
memset(book,0,sizeof(book));
tmp.x=0;
tmp.y=0;
tmp.z=s;
tmp.step=0;
book[s][0][0]=1;
q.push(tmp);
while(!q.empty())
{
tmp=q.front();
q.pop();
if(((tmp.x==tmp.y)&&tmp.z==0)||((tmp.x==tmp.z)&&tmp.y==0)||((tmp.y==tmp.z)&&tmp.x==0)) {
cout<<tmp.step<<endl;
flag=1;
break;
}
if(tmp.x<n&&tmp.z>0)
{
t.x=min(n,tmp.z+tmp.x);
t.y=tmp.y;
t.z=tmp.z-(t.x-tmp.x);
t.step=tmp.step+1;
if(book[t.z][t.x][t.y]==0)
{
book[t.z][t.x][t.y]=1;
q.push(t);
}
}
if(tmp.y<m&&tmp.z>0)
{
t.y=min(m,tmp.z+tmp.y);
t.x=tmp.x;
t.z=tmp.z-(t.y-tmp.y);
t.step=tmp.step+1;
if(book[t.z][t.x][t.y]==0)
{
book[t.z][t.x][t.y]=1;
q.push(t);
}
}
if(tmp.z<s&&tmp.x>0)
{
t.z=tmp.z+tmp.x;
t.y=tmp.y;
t.x=0;
t.step=tmp.step+1;
if(book[t.z][t.x][t.y]==0)
{
book[t.z][t.x][t.y]=1;
q.push(t);
}
}
if(tmp.z<s&&tmp.y>0)
{
t.z=tmp.z+tmp.y;
t.y=0;
t.x=tmp.x;
t.step=tmp.step+1;
if(book[t.z][t.x][t.y]==0)
{
book[t.z][t.x][t.y]=1;
q.push(t);
}
}
if(tmp.x>0&&tmp.y<m)
{
t.y=min(m,tmp.y+tmp.x);
t.z=tmp.z;
t.x=tmp.x-(t.y-tmp.y);
t.step=tmp.step+1;
if(book[t.z][t.x][t.y]==0)
{
book[t.z][t.x][t.y]=1;
q.push(t);
}
}
if(tmp.x<n&&tmp.y>0)
{
t.x=min(n,tmp.x+tmp.y);
t.y=tmp.y-(t.x-tmp.x);
t.z=tmp.z;
t.step=tmp.step+1;
if(book[t.z][t.x][t.y]==0)
{
book[t.z][t.x][t.y]=1;
q.push(t);
}
}
}
}
if(!flag)
{
cout<<"NO"<<endl;
}
}
return 0;
}
|
N- Find A Way
![14.1]( "14.1")
![14.2PNG]( "14.2PNG")
![14.2PNG]( "14.2PNG")
两次bfs，使用三维数组记录每个kfc到两者的时间之和，遍历之后取时间和最短的作为结果输出，需要注意的是有的kfc只有一个人能到达，因而初始化时需要注意。
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
|
#include<iostream>
#include<string.h>
#include<queue>
#include<algorithm>
#define MAXN 300
using namespace std;
char map[MAXN][MAXN];
int n,m;
int vis[MAXN][MAXN][2];
int vis1[MAXN][MAXN];
int vis2[MAXN][MAXN];
struct node{
int x,y,s;
};
int dir[4][2]={{0,-1},{-1,0},{0,1},{1,0}};
queue<node> q;
void bfs1(int x,int y)
{
vis1[x][y]=1;
node tmp;
tmp.x=x;
tmp.y=y;
tmp.s=0;
q.push(tmp);
while(!q.empty())
{
tmp=q.front();
q.pop();
if(map[tmp.x][tmp.y]=='@')
{
vis[tmp.x][tmp.y][0]=tmp.s*11;
}
for(int i=0;i<4;i++)
{
int tmpx,tmpy,tmps;
tmpx=tmp.x+ dir[i][0];
tmpy=tmp.y+dir[i][1];
tmps=tmp.s+1;
if(!vis1[tmpx][tmpy]&&(map[tmpx][tmpy]=='.'||map[tmpx][tmpy]=='@')&&tmpx>=0&&tmpy>=0&&tmpx<n&&tmpy<m)
{
vis1[tmpx][tmpy]=1;
node in;
in.x=tmpx;
in.y=tmpy;
in.s=tmps;
q.push(in);
}
}
}
}
void bfs2(int x,int y)
{
vis2[x][y]=1;
node tmp;
tmp.x=x;
tmp.y=y;
tmp.s=0;
q.push(tmp);
while(!q.empty())
{
tmp=q.front();
q.pop();
if(map[tmp.x][tmp.y]=='@')
{
vis[tmp.x][tmp.y][1]=tmp.s*11;
}
for(int i=0;i<4;i++)
{
int tmpx,tmpy,tmps;
tmpx=tmp.x+ dir[i][0];
tmpy=tmp.y+dir[i][1];
tmps=tmp.s+1;
if(!vis2[tmpx][tmpy]&&(map[tmpx][tmpy]=='.'||map[tmpx][tmpy]=='@')&&tmpx>=0&&tmpy>=0&&tmpx<n&&tmpy<m)
{
vis2[tmpx][tmpy]=1;
node in;
in.x=tmpx;
in.y=tmpy;
in.s=tmps;
q.push(in);
}
}
}
}
int main()
{
while(cin>>n>>m)
{
int inx1,iny1,inx2,iny2;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>map[i][j];
if(map[i][j]=='Y')
{
inx1=i;
iny1=j;
}
if(map[i][j]=='M')
{
inx2=i;
iny2=j;
}
}
}
memset(vis,-1,sizeof(int)*MAXN*MAXN*2);
memset(vis1,0,sizeof(int)*MAXN*MAXN);
memset(vis2,0,sizeof(int)*MAXN*MAXN);
bfs1(inx1,iny1);
while(!q.empty())
{
q.pop();
}
bfs2(inx2,iny2);
int min=4000003;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(map[i][j]=='@')
{
if((vis[i][j][0]+vis[i][j][1]<min)&&(vis[i][j][0]!=-1&&!vis[i][j][1]!=-1))
{
min=vis[i][j][0]+vis[i][j][1];
}
}
}
}
cout<<min<<endl;
}
}
|
