相关知识总结

训练题讲解

题克隆自传说中“ OIer 都会做的专题”—— Vjudge 上的[kuangbin带你飞]专题一 简单搜索，目前还差一道题就 AK 了，写这篇文章的初衷主要是纪念一下这个艰辛又快（痛）乐（苦）的经历，其次是为了沉淀一下这几天关于搜索题的感悟

棋盘问题—DFS

题意：在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放 k 个棋子的所有可行的摆放方案

思路： 参考博客  最简单的方法就是回溯 DFS 求解，我们可以从第一行的每个位置尝试放棋子（也可能不放），然后开一个 vis 记录每一列是否存在棋子。在第一行的某个位置放下就尝试在下一行放棋子（也可能不放），如此不断深度搜索就可以找到方法数量了。至于如何算上当前行不放的情况的方法数量，那就在搜索完当前行每个位置放棋子后再加一个跳过当前行直接搜索下一行的操作，此题坑点在于用回溯处理遍历每一行各位置时各列的标记回溯问题，详情见代码

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int n,k,cnt,sum;//棋盘长度，下棋数量，DFS下棋统计和情况统计
char chest[10][10];//棋盘
bool vis[10];//统计当前列是否已经存在棋子

void init(){
	memset(chest,0,sizeof chest);
	memset(vis,0,sizeof vis);
	cnt=0;sum=0;
}

void dfs(int row){
	if(sum==k){
		cnt++;return ;//返还边界
	}
	if(row>n)return ;//终止边界
	for(int i=1;i<=n;i++){
		if(!vis[i]&&chest[row][i]=='#'){
			vis[i]=1;//当前列标记
			sum++;//放一颗棋子
			dfs(row+1);//走下一行

            //回溯操作
			vis[i]=0;//还原该列下次再走到该列是重新走了，假如第1行有两个#当从第1行的第一个#开始往下走时,假设第2行中有且只有一个#,并且不与第一行中的任意一个在同一列，那么再往下
			sum--;/*走时就会把这个#标记 当递归返回到第一行第一个#时 i会++ 到第一行的第2个# 函数继续会继续往下走,到达第2行的那个#，因为在第一行第一个#那条路径中
            已经走过了第2行的那个#(因为第2行只有一个#并且这个#所在的列数不与第一行两个#重合),如果不把第一次走过第二行的#的标记消除  那么这次路径就不会再过第二行的
            这个# 那么可选路径少了肯定不对了*/
		}
	}
	dfs(row+1);//关键:上面都是遍历每列尝试选取某个位置往下递归，但是还有可能不选，所以最后还多再多遍历一种情况
}

signed main()
{
	ios::sync_with_stdio(false),cin.tie(0);
	while(cin>>n>>k){
		if(n==-1&&k==-1)break;
		init();
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				cin>>chest[i][j];
		dfs(1);//从第一行开始尝试下棋
		cout<<cnt<<endl;
	}
	return 0;
}

Dungeon Master—BFS

题意：典型走迷宫问题，只不过将二维转为的三维，你可以上下左右前后六个方向走。给出层数、行数和列数，迷宫图中.可以走，#不可以走，求出起点 S 到终点 E 的最短时间

思路：注意细节就好：一是存图多字符要吃空格，二是有可能走不出迷宫，所以设一个变量 flag 记录 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
#include<bits/stdc++.h>
using namespace std;
const int maxn=35;

int ll,rr,cc;
int rs,ys,xs,re,ye,xe;

char chest[maxn][maxn][maxn];
bool vis[maxn][maxn][maxn];

struct pos{
	int r,x,y,ans;
};

const int dir[6][3]={
	{1,0,0},{-1,0,0},{0,0,-1},{0,0,1},{0,-1,0},{0,1,0}
};

bool check(pos p){
	if(!vis[p.r][p.y][p.x]&&p.r>=1&&p.y>=1&&p.x>=1&&p.r<=ll&&p.y<=rr&&p.x<=cc)
	return 1;
	return 0;
}

void bfs(){
	bool flag=0;
	int time;
	pos start;
	queue <pos> q;
	start.r=rs;
	start.y=ys;
	start.x=xs;
	start.ans=0;
	q.push(start);
	vis[rs][ys][xs]=1;
	while(!q.empty()&&!flag){
		pos now=q.front();
		q.pop();
		pos nex=now;
		for(int i=0;i<6;i++){
			nex.r=now.r+dir[i][0];
			nex.y=now.y+dir[i][1];
			nex.x=now.x+dir[i][2];
			nex.ans=now.ans+1;
			if(check(nex)){
				if(nex.r==re&&nex.y==ye&&nex.x==xe){
					time=nex.ans;
					flag=1;//标记找到终点
					break;
				}
				q.push(nex);
				vis[nex.r][nex.y][nex.x]=1;
			}
		}
	}
	if(flag)
	cout<<"Escaped in "<<time<<" minute(s)."<<endl;
	else
	cout<<"Trapped!"<<endl;
}

signed main()
{
	while(cin>>ll>>rr>>cc){
		memset(vis,0,sizeof(vis));
		if(ll==rr&&rr==cc&&cc==0)
		break;
		for(int i=1;i<=ll;i++){
			for(int y=1;y<=rr;y++){
				for(int x=1;x<=cc;x++){
					cin>>chest[i][y][x];
					if(chest[i][y][x]=='S')
					rs=i,ys=y,xs=x;
					if(chest[i][y][x]=='E')
					re=i,ye=y,xe=x;
					if(chest[i][y][x]=='#')
					vis[i][y][x]=1;
				}
				getchar();
			}
			getchar();
		}
		bfs();
	}
	return 0;
}

Catch That Cow—BFS

题意：和 B 题正好相反这题改为一维的走迷宫问题，老农要抓奶牛，开始输入 N（老农的位置）和 K（奶牛的位置）老农有三种移动方法：一是向前走一步耗时一分钟，二是向后走一步耗时一分钟，三是向前移动到当前位置的两倍 N*2 耗时一分钟。问老农抓到奶牛的最少时间，途中奶牛的位置不变

思路：也是注意一个细节：就是老农的最短路径中可能先超过了奶牛的位置后来又折返向回走，所以数组 vis 要开大一点，当然了也没必要开太大因为走那么远了肯定不是耗时最短的路径了

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;//坐标的最大值

int n,k;
bool vis[N];

struct pos{
    int x,time;//走到的当前位置的坐标和用的时间
};

void init(){
    memset(vis,0,sizeof vis);
}

inline bool check(int x){//不超过边界且没走过
    if(x>=N||x<0||vis[x]==1)return 0;//x太大也不行
    return 1;
}

int bfs(){
    pos start;
    start.x=n,start.time=0;
    queue<pos> q;
    q.push(start);

    while(!q.empty()){
        pos now=q.front();
        q.pop();
        if(now.x==k){
            return now.time;
        }

        //向前一步走
        pos nex=now;
        nex.x=now.x+1,nex.time=now.time+1;
        if(check(nex.x)){
            q.push(nex);
            vis[nex.x]=1;
        }

        //向后一步走
        nex.x=now.x-1,nex.time=now.time+1;
        if(check(nex.x)){
            q.push(nex);
            vis[nex.x]=1;
        }
        
        //第二种方式走
        nex.x=now.x*2,nex.time=now.time+1;
        if(check(nex.x)){
            q.push(nex);
            vis[nex.x]=1;
        }

    }

    return -1;//走不到返还-1
}

signed main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    while(cin>>n>>k){
        init();
        cout<<bfs()<<endl;
    }
    return 0;
}

Fliptile—BFS

题意：n*m 的矩阵，全是 0 和 1 构成的（ 0 代表白色 1 代表黑色），当选择翻一个瓦块的时候，周围的瓦块会受到影响也翻面，问选择翻 n*m 矩阵中的哪些瓦块，可以将所有点均翻为白色，要求翻面操作尽可能少

思路： 参考博客  这题是个综合题有点难，首先我们推一下过程，那么对于第一行，它不能通过只对这一行进行反转得到全白色瓦块，它只能通过第二行和第一行的反转进行结合，来让第一行的黑色瓦块变成白色瓦块。而对于最后一行的黑色瓦块，也只能通过倒数第二行和本行的结合让其中的黑色瓦块全部变成白色瓦块

所以我们的方法是，先将第一行的所有可能的反转情况全部逆字典序地进行枚举，这样我们就可以在同为最少步骤的时候，不需要再进行判断了，因为在同一反转次数下，逆字典序最小的先得出了。然后我们对第二行进行枚举，若在某一列的上方，比如 (2,4) 和 (1,4) ，如果上方有黑色的瓦块，那么只有通过这个位置的瓦块（此处为 (2,4) ）进行反转，才可以让上方的瓦块变成白色。那么倒数第二行就很关键了，因为这一行造成的反转不仅要让倒数第三行的黑色瓦块变成白色瓦块，同时也要让最后一行的黑色瓦块变成白色瓦块，所以当我们利用最后一行，让倒数第二行的黑色瓦块全部变成了白色瓦块之后：如果此时最后一行的瓦块不全是白色的，说明这一操作的不成功，如果通过上面的操作让整个地图变成了白色的话，就说明这一反转的方法可以成功

另外观察数据发现最大不超过 15 ，在结合逆字典序所以我们可以把第一行的枚举状态改用状压枚举

这份代码测了几个样例但是还是没能 AC ，不知道哪里 RE 了，题的链接里有参考代码

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=21;
const int inf=1e9+5;

int n,m;
bool chest[N][N],ans[N][N];//初始地图和答案
bool t[N][N],vis[N][N];//临时图和临时答案

void flips(int x,int y){//自身及四周瓦块翻转
    t[x][y]=!t[x][y];
    t[x-1][y]=!t[x-1][y];
    t[x+1][y]=!t[x+1][y];
    t[x][y-1]=!t[x][y-1];
    t[x][y+1]=!t[x][y+1];
}

inline bool judge(){//判断最后一行是不是全部白色朝上
    for(int i=1;i<=m;i++)
    if(t[n][i]==1)return 0;
    return 1;
}

int work(int cnt){
    for(int i=2;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(t[i-1][j]==1){
                vis[i][j]=1;
                flips(i,j);
                cnt++;
            }
        }
    }
    if(judge())return cnt;
    return inf;
}

void solve(){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        cin>>chest[i][j];

    int minstep=inf;//最小步数
    for(int i=0;i<(1<<m);i++){//状压枚举第一行的状态
        memcpy(t,chest,sizeof t);//复制一份地图
        memset(vis,0,sizeof vis);
        int cnt=0;//统计需要翻转的步数
        for(int j=0;j<m;j++){//查看每个位置的当前状态
            if(i&(1<<j)){
                vis[i][j+1]=1;//当前位置翻转并且标记
                flips(1,j+1);//当前位置四周翻转
                cnt++;
            }
        }
        
        cnt=work(cnt);//加上后面需要翻转的步数
        if(cnt<minstep){//2~n行翻转并尝试更新最小步数
            minstep=cnt;
            memcpy(ans,vis,sizeof vis);
        }
    }

    if(minstep==inf){
        cout<<"IMPOSSIBLE"<<endl;
        return ;
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            cout<<ans[i][j]<<" ";
        cout<<endl;
    }
}

signed main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    while(cin>>n>>m){
        solve();
    }
    return 0;
}

Find The Multiple—DFS/BFS

题意：给出一个整数 n（ 1<=n<=200 ）。求出任意一个它的倍数 m ，要求 m 必须只由十进制的 0 或 1 组成

思路： 参考博客  找规律的 DFS ，但是由于测评姬的样例太水了直接暴力 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
include<bits/stdc++.h>
using namespace std;

int n;
string t,res;

bool dfs(int mod) {
	if (t.size()>100)
    return false;
	if(mod==0){ 
        res=t; 
        return true; 
    }

	t+='0';
	if(dfs((mod*10)%n))
	return true;
	t.erase(t.size()-1,1);
	t+='1';
	if(dfs((mod *10+1)%n))
	return true;
	t.erase(t.size()-1,1);
	return false;
}

signed main(){
	while(cin>>n&&n){
		t.clear();res.clear();
		t+='1';
		dfs(1);
		cout<<res<<endl;
	}
    return 0;
}

暴力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
//测试样例最大不超过1e19，别问为什么网上查的
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int n;

ll bfs(){
	queue<ll> q;
	ll now=1,nex;
	q.push(now);
	while(!q.empty()){
		now=q.front();
		q.pop();
		if(now%n==0)
		return now;
		if(now>1e19)//终止边界
		return 0;

		nex=now*10;
		q.push(nex);
		nex=now*10+1;
		q.push(nex);
	}
	return 0;
}
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0);
	while(cin>>n&&n){
		cout<<bfs()<<endl;
	}
	return 0;
}

Prime Path—BFS

题意：给定两个素数 a 和 b（保证都是4位数），求 a 转变到 b 需要几步，能转变的数要求和原a都是素数并且位数上只有一位不同

思路：不难想到的是 BFS 搜索 a 到 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
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn=1e4+5;

int a,b,zz;//a到b,素数筛找到的素数
int prime[maxn];//存素数的数组
bool is_prime[maxn+1],vis[maxn];//vis标记状态是否走过

struct node{
    int val,step;
};

void init(){
    memset(is_prime,0,sizeof is_prime);
    memset(vis,0,sizeof vis);
}

//返回n以内素数的个数
int sieve(int n){
    int p=0;
    for(int i=0;i<=n;i++)is_prime[i]=true;
    is_prime[0]=is_prime[1]=false;
    for(int i=2;i<=n;i++){
        if(is_prime[i]){
            if(i>=1000)prime[p++]=i;//打表1000及以上的素数
            for(int j=2*i;j<=n;j+=i)is_prime[j]=false;//筛去所有素数的倍数
        }
    }
    return p;
}

bool judge(int x,int y){//判断x和y是否只有一位不同
    bool flag=0;
    while(x!=0){
        int temp1=x%10,temp2=y%10;
        if(temp1!=temp2){
            if(flag==1)return 0;
            else flag=1;
        }
        x/=10,y/=10;
    }
    return 1;
}

int bfs(){
    queue<node> q;
    node st;
    st.val=a,st.step=0;
    vis[st.val]=1;
    q.push(st);
    while(!q.empty()){
        node now=q.front();
        q.pop();
        if(now.val==b)return now.step;
        for(int i=zz-1;i>=0;i--){//根据贪心尽量往大了转变
            node nex=now;
            if(vis[prime[i]]==0&&judge(now.val,prime[i])){//状态没走过并且当前的数和找到的素数只相差一位
                vis[prime[i]]=1;
                nex.val=prime[i];
                nex.step=now.step+1;
                q.push(nex);
            }
        }
    }
    return -1;
}

void solve(){
    cin>>a>>b;
    int ans=bfs();
    if(ans==-1)cout<<"Impossible"<<endl;
    else cout<<ans<<endl;
}

signed main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    int t;cin>>t;
    zz=sieve(maxn);
    //for(int i=0;i<p;i++)cout<<prime[i]<<" ";
    while(t--){
        init();
        solve();
    }
    return 0;
}

Shuffle’m Up—模拟+map容器

题意：已知两堆牌 s1 和 s2 的初始状态， 其牌数均为 c ，按给定规则能将他们相互交叉组合成一堆牌 s12 ，再将 s12 的最底下的 c 块牌归为 s1 ，最顶的 c 块牌归为 s2 ，依此循环下去。现在输入 s1 和 s2 的初始状态 以及 预想的最终状态 s 。问 s1 和 s2 经过多少次洗牌之后，最终能达到状态 s12 ，若永远不可能相同，则输出 -1

思路：准确的说这题根本不是搜索专题的题，出在这里可能是因为模拟的过程和 DFS 有点像吧（或者说是思维相似），开一个 map 存储出现的每一个 s12 ，如果 s12==s 就找到了，如果 s12 在 map 中说明循环重复了永远也找不到输出 -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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int cases,n;
string s1,s2,s12,targ;//s1,s1和目标字符串
map<string,int> mp;//动态数组记录字符串是否循环中出现过

void solve(){
    mp.clear();//清空map
    int cnt=1;//统计循环次数

    cin>>n;
    cin>>s1>>s2>>targ;

    //一次混排
    s12.clear();//新技能:清空string
    for(int i=0;i<n;i++)
    s12+=s2[i],s12+=s1[i];
    if(s12==targ){
        cout<<++cases<<" "<<cnt<<endl;
        return ;
    }
    else mp[s12]++;

    while(1){//循环操作

        //重新获得s1,s2
        s1.clear(),s2.clear();
        for(int i=0;i<n;i++){
            s1+=s12[i],s2+=s12[i+n];
        }

        //一次混排
        cnt++;
        s12.clear();//新技能:清空string
        for(int i=0;i<n;i++)//注意：最底下的先给s2
        s12+=s2[i],s12+=s1[i];

        //处理结果
        if(s12==targ){
            cout<<++cases<<" "<<cnt<<endl;
            return ;
        }
        else{
            if(mp[s12]>0){//说明不可能实现
                cout<<++cases<<" "<<-1<<endl;
                return ;
            }
            else mp[s12]++;
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    int t;cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Pots—BFS

题意：有两个水壶，对水壶有三种操作，1) FILL(i) ，将 i 水壶的水填满，2) DROP(i) ，将水壶 i 中的水全部倒掉，3)POUR(i,j) ，将水壶 i 中的水倒到水壶 j 中，若水壶 j 满了，则 i 剩下的就不倒了，问进行多少步操作，并且怎么操作，输出操作的步骤，两个水壶中的水可以达到 C 这个水量。如果不可能则输出 impossible 。初始时两个水壶是空的没有水

思路：把 A 壶和 B 壶中储存的水量记为一个状态，那么初始状态就是 (0,0) ，总共有 6 个操作转向下一个状态，那么只要满足条件就去尝试（ 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
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=110;

int a,b,c;//记录a,b壶内水量,要求壶内装有的水量
bool vis[N][N];//记录a.b水杯的状态
string path[7]={
    "WA","FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"
};

//操作编号和记录状态经过的操作数组都从1开始记录
struct node{
    int a,b,level;//当前状态a.b杯里的水量以及经过的操作次数
    int len;//到当前状态进过的操作次数
    int road[N*2];//0~len-1保存到当前状态经过的每次操作序号
};

void printpath(int lvl,int p[],int n){//打印路径
    cout<<lvl<<endl;
    for(int i=1;i<=n;i++)
    cout<<path[p[i]]<<endl;
}

inline void init(){
    memset(vis,0,sizeof vis);
}

void solve(){
    queue<node> q;
    node st;
    st.a=0,st.b=0,st.level=0,st.len=0;
    memset(st.road,0,sizeof st.road);
    vis[st.a][st.b]=1;
    q.push(st);

    while(!q.empty()){
        node now=q.front();
        q.pop();
        if(now.a==c||now.b==c){//找到要求的状态
            printpath(now.level,now.road,now.len);
            return ;
        }

        node nex=now;
        nex.level=now.level+1;
        nex.len=now.len+1;

        //FILL(a)
        if(a-now.a>0){
            nex.a=a;
            nex.b=now.b;
            if(vis[nex.a][nex.b]==0){
                nex.road[nex.len]=1;
                q.push(nex);
                vis[nex.a][nex.b]=1;
            }
        }

        //FILL(b)
        if(b-now.b>0){
            nex.a=now.a;
            nex.b=b;
            if(vis[nex.a][nex.b]==0){
                nex.road[nex.len]=2;
                q.push(nex);
                vis[nex.a][nex.b]=1;
            }
        }

        //DROP(a)
        if(now.a>0){
            nex.a=0;
            nex.b=now.b;
            if(vis[nex.a][nex.b]==0){
                nex.road[nex.len]=3;
                q.push(nex);
                vis[nex.a][nex.b]=1;
            }
        }

        //DROP(b)
        if(now.b>0){
            nex.a=now.a;
            nex.b=0;
            if(vis[nex.a][nex.b]==0){
                nex.road[nex.len]=4;
                q.push(nex);
                vis[nex.a][nex.b]=1;
            }
        }

        //POUR(a,b)
        if(now.a>0&&now.b<b){
            if(now.a>(b-now.b)){
                nex.a=now.a-(b-now.b);
                nex.b=b;
            }
            else{
                nex.a=0;
                nex.b=now.a+now.b;
            }

            if(vis[nex.a][nex.b]==0){
                nex.road[nex.len]=5;
                q.push(nex);
                vis[nex.a][nex.b]=1;
            }
        }

        //POUR(b,a)
        if(now.b>0&&now.a<a){
            if(now.b>(a-now.a)){
                nex.a=a;
                nex.b=now.b-(a-now.a);
            }
            else{
                nex.a=now.a+now.b;
                nex.b=0;
            }

            if(vis[nex.a][nex.b]==0){
                nex.road[nex.len]=6;
                q.push(nex);
                vis[nex.a][nex.b]=1;
            }
        }
    }

    cout<<"impossible"<<endl;
}

signed main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    while(cin>>a>>b>>c){
        init();
        solve();
    }
    return 0;
}

Fire Game—双向BFS

题意：给出一个 m*n 的图，# 表示草坪，. 表示空地，然后可以选择在任意的两个草坪格子点火（选的两个点可以重合），火每秒会向周围四个格子扩散，问选择那两个点使得燃烧所有的草坪花费时间最小

思路：典型的双向 BFS 题，实际上就是出发点变为两个（同时压入队列），给每个点设置一个 time 记录走到当前所花时间（从个出发点到是未知的所以该属性是必要的）。观察数据发现最大不超过 10 ，所以就暴力枚举两个点进行 BFS ，注意的是题目答案要求：一是能够把所有草烧完，而是花费时间最少，所以从两个点进行 BFS 先看看能不能把所有草烧完，再同时统计时间并在要求一满足的条件下尝试更新答案

其实这里有一个小的优化，就是不用再另开 vis 数组标记节点是否访问过，因为访问过的点要么是出发点要么是 time 非 0 的点，所以借助 time 就可以判断点是否访问过

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=15;
const int inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{0,-1},{-1,0},{1,0}};

int n,m,sum,cases;//图的规格,草的数量以及样例数
char chest[N][N];
bool vis[N][N];

struct node{
    int x,y,time;//该节点的坐标和走过的时间
}s1,s2;//两个出发点

void init(){
    sum=0;
}

inline bool judge(node temp){//不越界、可同行并且未访问
    return temp.x>=1&&temp.x<=n&&temp.y>=1&&temp.y<=m&&vis[temp.x][temp.y]==0&&chest[temp.x][temp.y]=='#';
}

int bfs(int x1,int y1,int x2,int y2){
    memset(vis,0,sizeof vis);//一个样例多次BFS函数内部更新
    int num=0,maxx=0;//统计烧过的草的数量和烧完所用的时间
    queue<node> q;

    s1.x=x1,s1.y=y1,s2.x=x2,s2.y=y2;
    s1.time=s2.time=0;//到出发点所用时间为0
    vis[s1.x][s1.y]=vis[s2.x][s2.y]=1;
    q.push(s1),q.push(s2);//两个点压入队列同时走
    if(s1.x==s2.x&&s1.y==s2.y)num=1;
    else num=2;

    while(!q.empty()){
        node now=q.front();
        q.pop();

        for(int i=0;i<=3;i++){
            node nex=now;
            nex.x=now.x+dir[i][0];
            nex.y=now.y+dir[i][1];
            nex.time=now.time+1;
            if(judge(nex)){
                num++;//烧过的草+1
                if(nex.time>maxx)//更新烧草用的时间
                maxx=nex.time;

                q.push(nex);
                vis[nex.x][nex.y]=1;
            }
        }
    }

    if(num<sum)return inf;//草没权烧完不能作为答案返还inf
    else return maxx;//返还烧完所有草所用的时间
}

void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>chest[i][j];
            if(chest[i][j]=='#')
            sum++;
        }
    }

    int ans=inf;//记录答案
    for(int i1=1;i1<=n;i1++){
        for(int j1=1;j1<=m;j1++){
            if(chest[i1][j1]=='#')//选一个出发点
            for(int i2=1;i2<=n;i2++){
                for(int j2=1;j2<=m;j2++){
                    if(chest[i2][j2]=='#')//另一个出发点
                    ans=min(ans,bfs(i1,j1,i2,j2));//选择花费时间少的
                }
            }
        }
    }

    cout<<"Case "<<++cases<<": ";
    if(ans==inf)cout<<-1<<endl;
    else cout<<ans<<endl;
}

signed main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    int t;cin>>t;
    while(t--){
        init();
        solve();
    }
    return 0;
}

Fire!—BFS

  • [ ] 等着下辈子补题

迷宫问题—BFS

题意：一个 5×5 的二维数组，表示一个迷宫，其中 1 表示墙壁，0 表示可通行，只能上下左右四个方向移动，要求找出从左上角走到右下角的正确路线（题目保证正确路径唯一）并打印出路径

思路：典型 BFS 记录路径问题，显然，我们不能够直接从起点往终点开始搜，将每次可以走的地点立即输出。这样显然是不对的，因为可能从起点到终点有多个错误的分支。对此，我们采取的措施是反向搜索，即从终点玩起点搜索并且，我们将记录每一个可以走的点，到终点的距离（相当于给每个点打上时间戳）。然后，我们只需要再正向从起点遍历四周找比当前点小 1 的点作为下一个点，一直找到终点位置就是正确路径的顺序（好像是记录路径的一种方法，好多题都有用到该思想），为什么对呢？恰好是因为题目保证的正确路径唯一，所以沿着小于 1 的序号找到终点的路就保证了是正确路径（以下图 4*4 的迷宫示例）

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int vis[5][5],j[5][5];

struct pos{
    int x,y;
};

const int dir[4][2]={
    {-1,0},{1,0},{0,1},{0,-1}
};

bool check(pos temp){
    if(temp.x<0||temp.x>4)return false;
	if(temp.y<0||temp.y>4)return false;//判断是否越界 
	if(vis[temp.x][temp.y]==1)return false;//判断能否走和是否走过 
	return true;
}

void bfs(){
    queue<pos> q;
    pos start;
    start.x=4,start.y=4;
    q.push(start);
    j[4][4]=1;vis[4][4]=1;
    while(!q.empty()){
        pos now=q.front();
        q.pop();
        if(now.x==0&&now.y==0)
        return ;
        for(int i=0;i<4;i++){
            pos nex=now;
            nex.x=now.x+dir[i][0];
            nex.y=now.y+dir[i][1];
            if(check(nex)){
                q.push(nex);
                j[nex.x][nex.y]=j[now.x][now.y]+1;
                vis[nex.x][nex.y]=1;
            }
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    for(int i=0;i<5;i++)
        for(int j=0;j<5;j++)
            cin>>vis[i][j];
    bfs();

    cout<<"(0, 0)"<<endl;//输出起点
    int x=0,y=0;//记录当前所处位置
    while(x!=4||y!=4){//遍历找下一个点
        for(int i=0;i<4;i++){
            int tx=x+dir[i][0],ty=y+dir[i][1];
            if(tx>=0&&ty>=0&&ty<=4&&tx<=4){
                if(j[tx][ty]==j[x][y]-1){
                    x=tx;y=ty;//更新当前做出位置
                    cout<<"("<<tx<<", "<<ty<<")"<<endl;
                    break;
                } 
            }
        }
    }
    return 0;
}

Oil Deposits—BFS

题意：矩形图中 * 代表没有油的坑，@ 代表有油的坑，相邻的有油的坑被作为一个油藏，让找出图中有多少个油藏

思路：两种做法：一种就是枚举图中的节点，如果图中节点为@则将其作为起点 BFS 周围的 @ 并将访问的 @ 改为 *（这个方法不用另开数组）。另一种是不在图中更改访问的点，而是在 vis 数组中标记为访问过（需要另开一个标记数组 vis ）

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
#include<bits/stdc++.h>
using namespace std;
const int dir[8][2]={1,0,1,1,1,-1,0,1,0,-1,-1,0,-1,1,-1,-1};

int n,m;
char a[100][100];
int sum;

struct pos{
    int x;
    int y;
};
int check(int x,int y)
{
    if(x>=0&&x<n&&y>=0&&y<m)
    return true;
    return false;
}

void bfs(int x,int y){
    pos now,next;
    queue<pos> q;
    now.x=x;now.y=y;
    q.push(now);

    while(!q.empty()){
        now=q.front();
        q.pop();
        for(int i=0;i<8;i++){
            next.x=now.x+dir[i][0];
            next.y=now.y+dir[i][1];
            if(check(next.x,next.y)&&a[next.x][next.y]=='@'){
                a[next.x][next.y]='*';
                q.push(next);
            }
        }
    }
}

signed main()
{
    while(cin>>n>>m&&m){
        sum=0;
        for(int i=0;i<n;i++)cin>>a[i];
        
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(a[i][j]=='@'){
                    sum++;
                    bfs(i,j);
                }
            }
        }
       cout<<sum<<endl;
    }
    return 0;
}

非常可乐—数论

题意：大家一定觉的运动以后喝可乐是一件很惬意的事情，但是 seeyou 却不这么认为。因为每次当 seeyou 买了可乐以后，阿牛就要求和 seeyou 一起分享这一瓶可乐，而且一定要喝的和 seeyou 一样多。但 seeyou 的手中只有两个杯子，它们的容量分别是N 毫升和M 毫升 可乐的体积为 S(S<101) 毫升　(正好装满一瓶) ，它们三个之间可以相互倒可乐 (都是没有刻度的，且 S==N+M,101＞S＞0,N＞0,M＞0 ) 。聪明的 ACMER 你们说他们能平分吗？如果能请输出倒可乐的最少的次数，如果不能输出 NO

思路： 参考博客  BFS 看着挺复杂的，某位大佬用数论求出了规律

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

signed main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    int a,b,c;
    while(cin>>a>>b>>c){
        if(a==0&&b==0&&c==0)break;
        a/=__gcd(b,c);
        if(a%2!=0)cout<<"NO"<<endl;
        else cout<<a-1<<endl;
    }
    //system("pause");
    return 0;
}

Find a way—双向BFS

题意：兄弟俩分别在图中的 Y 和 M 点，他俩要去同一个 KFC 恰饭，图中有好多个 KFC 请找出俩人会面花费时间最少的 KFC 并输出 花费的时间*11

思路：和 Fire Game 有不一样了，这次不能一次性两个方向 BFS 因为好多的点，选的店不同俩人需要花费的时间不一样（而之前的题只要俩人其中一个到了就可以不用考虑），所以两个起点分别各做一次 BFS ，然后访问到 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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int N=210;
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};

int n,m;//n行m列
bool flag;//记录样例中第几次遍历
char chest[N][N];//记录初始棋盘
bool vis[N][N];//辅助BFS
int dis[N][N][2];//存储两人到KFC的最短距离，其他点都不存

struct pos{
    int x,y;
    int step;
}s1,s2;

void init(){//每次样例的初始化
    memset(dis,inf,sizeof dis);
    flag=0;
}

inline bool judge(pos temp){//不出界、没走过并且1可以通行
    return temp.x>=1&&temp.x<=n&&temp.y>=1&&temp.y<=m&&chest[temp.x][temp.y]!='#'&&vis[temp.x][temp.y]==0;
}

void bfs(pos st){//一次样例跑两边所以初始化放里面
    memset(vis,0,sizeof vis);
    queue<pos> q;

    st.step=0;//设到当前出发位置为0
    vis[st.x][st.y]=1;
    q.push(st);

    while(!q.empty()){
        pos now=q.front();
        q.pop();

        for(int i=0;i<4;i++){//朝四个方向走
            pos nex=now;
            nex.step=now.step+1;
            nex.x=now.x+dir[i][0],nex.y=now.y+dir[i][1];

            if(judge(nex)){//如果符合状态就走到下一个地方
                vis[nex.x][nex.y]=1;

                if(chest[nex.x][nex.y]=='@')//是KFS记录到对应的dis中
                dis[nex.x][nex.y][flag]=nex.step;

                q.push(nex);
            }
        }

    }
}

void solve(){
    //从1开始存
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>chest[i][j];
            if(chest[i][j]=='Y')//记录两个人的位置
            s1.x=i,s1.y=j;
            else if(chest[i][j]=='M')
            s2.x=i,s2.y=j;
        }
    }

    bfs(s1);//先算出s1到各KFC的最短距离并存入对应的dis[][][0]中
    flag=1;//标记表示开始走s2存入dis[][][1]
    bfs(s2);

    int ans=inf;//找最小值的答案
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(chest[i][j]=='@'){//KFC就进行更新
                ans=min(dis[i][j][0]+dis[i][j][1],ans);
            }
        }
    }
    cout<<ans*11<<endl;
}

signed main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    while(cin>>n>>m){
        init();
        solve();
    }
    return 0;
}