搜索专题第22组题解

写题之前你至少要搞懂深搜，广搜的原理，队列（先进先出）和栈（后进先出）的特点

深搜用堆栈存储，深搜的路径像面条一样，牺牲时间换空间，适用于求全部解的题等

广搜用队列存储，广搜的路径像水波一样，是往四周蔓延的，牺牲空间换时间，适用于求最短解的题等

A - 棋盘问题

建议先看全排列 
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 vis[30],n,k,sum,m;
char a[30][30];
void dfs(int p){
	if(k==m){
		sum++;
		return;
	}
	if(p>=n)
	return;
	for(int j=0;j<n;j++){
		if(vis[j]==0&&a[p][j]=='#'){
			vis[j]=1;//依旧先标记后复原
			m++;
			dfs(p+1);
			vis[j]=0;
			m--;
		}
	}
	dfs(p+1);
}
int main()
{
	while(scanf("%d%d",&n,&k)&&n!=-1&&k!=-1){
		sum=0;
		m=0;
		for(int i=0;i<n;i++)
		scanf("%s",&a[i]);
		dfs(0);
		printf("%d\n",sum);
	}
	return 0;
}

B - Perket

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 flag[11]={0};
int a[11],b[11];
int c=1,y=0;
int N;
int ans=1e11;
void dfs(int x){
	if(x>=N) 
	return;
	else{
		for(int i=0;i<N;i++){
			if(flag[i]==0){
				c*=a[i];//依旧先标记后复原
				y+=b[i];
				flag[i]=1;
				ans=min(ans,abs(c-y));
				dfs(i+1);
				c/=a[i];
				y-=b[i];
				flag[i]=0;
			}
		}
	}
}
int main(){
	cin>>N;
	for(int i=0;i<N;i++){
		cin>>a[i]>>b[i];
	}
	dfs(0);
	cout<<ans;
	return 0;
}

C - 全排列

这里是字符全排列，不过和数字全排列没什么区别，用深搜遍历出每一种可能就行了，如果想省事，用c++里的next_permutation()函数就行了。

像这种经典题如果是第一次见，搞懂然后记住就完了 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char a[25],b[25];//用a数组读入字符串，b数组记下路径
int n,vis[25];//标记数组，搜索过的数就标记好，防止重复
void dfs(int p){
	if(p==n){
		b[n]='\0';
		cout<<b<<endl;//可以这样输出字符串
	}
	for(int i=0;i<n;i++)//如果函数调用到第m层，for循环实际上也在dfs前进入到了第m轮，那剩下的(n-m)轮呢，就是用来产生分支的
		if(!vis[i]){
			vis[i]=1;//dfs前做好标记（记住）
			b[p]=a[i];
			dfs(p+1);
			vis[i]=0;//dfs后删除标记,不同排列有相同数字，走的时候要取消标记（记住）
		}
} 
int main(){
	scanf("%s",a);
	n=strlen(a);
	dfs(0);//习惯上可以从0/1开始，和for循环里i的初值保持一致
	return 0;
}

D - 自然数拆分

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
#include<bits/stdc++.h>
using namespace std;
int a[41],s,m;
void pr(int s)
{
	cout<<m<<'=';
    for(int i=1;i<=s-2;i++)
	printf("%d+",a[i]);
    printf("%d\n",a[s-1]);
}
void dfs(int n,int s,int pre)//pre确保要减的数是递增的
{
    if(n==0&&s>1){//结束条件：进行至少一轮并且减完为零
        pr(s);
        return;
    }
    for(int i=pre;i<=n;i++){
        a[s]=i;
        dfs(n-i,s+1,i);
    }
}
int main()
{
    cin>>m;
    dfs(m,1,1);
    return 0;
}

E - Prime Ring Problem

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<bits/stdc++.h>
using namespace std;
int n,a[17],id=0;
bool vis[17];
bool prime(int n){
    for(int i=2;i<= sqrt(n);i++){
        if(n % i == 0) 
		return false;
    }
    return true;
}
void dfs(int x){
    if (x>n&&prime(a[x-1]+a[1])){//要判断第一个数和最后一个数的和是否为素数
        for(int i=1;i<=n;i++){
            cout<<a[i];
            if (i!=n)
			cout<<" ";
        }
        cout<<endl;
        return;
    }
    for(int i=1;i<=n;i++){
        if(prime(i+a[x-1])&&!vis[i]){
            vis[i]=true;
            a[x]=i;
            dfs(x+1);
            vis[i]=false;
        }
    }
}
int main()
{
	int t=0;
    while(cin>>n){
    	t++;
    	if(t>=2)
    	cout<<endl;
        cout<<"Case "<<++id<<":\n";
        memset(vis,false,sizeof(vis));
        a[1]=1;
        vis[1]=true;
        dfs(2);
    }
    return 0;
}

F - Red and Black

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
#include<bits/stdc++.h>
using namespace std;
int W,H;
char a[21][21];
int f(int x,int y){
    if (x<0||x>=W||y<0||y>=H)
        return 0;
    if (a[x][y]=='#'){
        return 0;
    }else{
        a[x][y]='#';
        return 1 + f(x-1,y)+f(x+1,y)+f(x,y-1)+f(x,y+1);//求所以可走的路径，将和相加
    }
}
int main()
{
    int i,j,num;
    while(scanf("%d%d",&H,&W)&&W!=0&&H!=0){
        for(i=0;i<W;i++)
            scanf("%s",a[i]);
        for(i=0;i<W;i++)
            for(j=0;j<H;j++)
                if(a[i][j]=='@') 
				printf("%d\n",f(i, j));
    }
    return 0;
}

G - Knight Moves

提醒一点，万能头虽好用，但里面有很多关键字可能会和你的变量名冲突，比如list,visit

这道题应该用广搜，不知道c++队列操作的自行了解一下

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
#include<bits/stdc++.h>
using namespace std;
const int len=302;
struct horse{
    int x;
    int y;
    int step;
};
bool Visit[len][len];
const int way[8][2]={{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1}};
void bfs(int s1,int e1,int s2,int e2,int lenth){
    queue<horse> q;
    horse start,now,next;
    start.x=s1;
    start.y=e1;
    start.step=0;
    Visit[start.x][start.y]=true;
    q.push(start);
    while(!q.empty()){
        now=q.front();
        q.pop();
        if(now.x==s2&&now.y==e2){
            cout<<now.step<<endl;
            return;
        }
        for(int i=0;i<8;i++){
            next.x=now.x+way[i][0];
            next.y=now.y+way[i][1];
            if(next.x>=0&&next.x<lenth&&next.y>=0&&next.y<lenth&&!Visit[next.x][next.y]){
                next.step=now.step+1;
                q.push(next);
                Visit[next.x][next.y]=true;
            }
        }
    }
}
int main()
{
    int n;
    cin>>n;
    int l;
    int x1,x2,y1,y2;
    for(int i=0;i<n;i++){
        cin>>l;
        cin>>x1>>y1;
        cin>>x2>>y2;
        memset(Visit,false,sizeof(Visit));
        bfs(x1,y1,x2,y2,l);
    }
    return 0;
}

H - Oil Deposits

这个题就是求矩阵中有多少个“分开”的区域，还可以变形为求最大面积等等

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
#include<bits/stdc++.h>
using namespace std;
char a[1000][1000];
int n,m;
void dfs(int x,int y){
    int i,j,b,c;
    for(i=-1;i<=1;i++){//这个写法爱了，这就是用循环表示8个方向
        for(j=-1;j<=1;j++){
            b=i+x;
            c=y+j;
            if(b>=0&&b<n&&y>=0&&y<m&&a[b][c]=='@'){//如果遇到@就开始搜索并且把@变为*
                a[b][c]='*';//这也算是一种标记
                dfs(b,c);
            }
        }
    }
}
int main()
{
    int i,j,cnt=0;
    while(scanf("%d %d",&n,&m)!=EOF&&n!=0&&m!=0){
        memset(a,'0',sizeof(a));//学会用memset初始化数组，因为是字符数组，全初始化为字符0，防止上一轮残留数据的干扰
        cnt=0;
        for(i=0;i<=n-1;i++)
            scanf("%s",a[i]);
        for(i=0;i<=n-1;i++){
            for(j=0;j<=m-1;j++){
                if(a[i][j]=='@'){
                    cnt++;//遇到油层就要计数
                    dfs(i,j);
                }
            }
        }
        printf("%d\n",cnt);
    }
}

I - Lake Counting

跟上一题一模一样，就是把@换成了w，*换成了.，并且无输入结束标志。

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
#include<bits/stdc++.h>
using namespace std;
char a[1000][1000];
int n,m;
void dfs(int x,int y){
    int i,j,b,c;
    for(i=-1;i<=1;i++){
        for(j=-1;j<=1;j++){
            b=i+x;
            c=y+j;
            if(b>=0&&b<n&&y>=0&&y<m&&a[b][c]=='W'){
                a[b][c]='.';
                dfs(b,c);
            }
        }
    }
}
int main()
{
    int i,j,cnt=0;
    while(scanf("%d %d",&n,&m)!=EOF){
        memset(a,'0',sizeof(a));
        cnt=0;
        for(i=0;i<=n-1;i++)
            scanf("%s",a[i]);
        for(i=0;i<=n-1;i++){
            for(j=0;j<=m-1;j++){
                if(a[i][j]=='W'){
                    cnt++;
                    dfs(i,j);
                }
            }
        }
        printf("%d\n",cnt);
    }
}

J - 二叉树先序遍历

不知道什么是二叉数和先序遍历的先去查查，已经在计导书里学过了，思路很简单，定义一个包含左右节点的结构体，如果树非空，就做三个操作：

1：输出节点；

2：先遍历左子树；

3：之后遍历右子树，如果为空就返回上一层；

像这种经典题如果是第一次见，搞懂然后记住就完了 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
struct p{
	int l;
	int r;
}t[100010];
void dfs(int x){
	if(x==0)
	return;
	cout<<x<<endl;//第1步
	dfs(t[x].l);//第2步
	dfs(t[x].r);//第3步
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>t[i].l>>t[i].r;//依次读入左右节点
	dfs(1);
	return 0;
}

之后在学数据结构的时候还有中序遍历、后序遍历，实现思路差不多

K - 迷宫（一）

学会用数组表示方向，不一定要二维数组，两个一维的也行，甚至可以用循环表示

像这种经典题如果是第一次见，搞懂然后记住就完了 
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
#include<bits/stdc++.h>
using namespace std;
int n,m;
bool f;
char mp[15][15];
int vis[15][15];
int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};//定义一个二维数组存方向，比如说(x-1,y+0)就是向上一个单位，使用方便
bool in(int x, int y)
{
    return 0<=x&&x<n&&0<=y&&y<m;
}
void dfs(int x, int y)
{
    if (mp[x][y]=='T'){//结束标志
        f=true;
        return;
    }
    if (!in(x,y)||mp[x][y]=='*'||vis[x][y]){
        return;//看看有没有越界，撞墙，走过
    }
    vis[x][y]=1;//dfs前做好标记，不能再走以前的路，所以不用再消除标记
    for (int i = 0; i < 4; i++){
        int tx=x+dir[i][0];//移动坐标
        int ty=y+dir[i][1];
        dfs(tx,ty);
    }
    return;
}
int main()
{
	scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        scanf("%s",mp[i]);
    }
    int x,y;
    for(int i=0;i<n;i++){
       for(int j=0;j<m;j++){
           if(mp[i][j]=='S'){
               x=i;//先找到开始搜索的点
               y=j;
           }
       }
    }
    dfs(x,y);
    if(f){
        printf("yes\n");
    }else{
        printf("no\n");
    }
	return 0;
}

L - 马走日

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
#include<bits/stdc++.h>
using namespace std;
int f[21][22],n,m,t;
int xx[10]={-2,-2,-1,1,2,2,1,-1};//用两个数组表示方向，也就是坐标变化
int yy[10]={-1,1,2,2,1,-1,-2,-2};
int x,y,ans;
void dfs(int a,int b){
    bool p=true;
    for(int i=1;i<=n;i++){//判断是不是走过了所有点
        for(int j=1;j<=m;j++){
            if(f[i][j]==0){
                p=false;
                break;
            }
        }
    }
    if(p==true){
        ans++;
        return;
    }
    for(int i=0;i<=7;i++){
        int l=a+xx[i];
        int k=b+yy[i];
        if(f[l][k]==1)
            continue;
        if(l>0&&l<=n&&k>0&&k<=m){ 
            f[l][k]=1;
            dfs(l,k);
            f[l][k]=0;
        }
    }
}
int main()
{
    scanf("%d",&t);
    for(int i=1;i<=t;i++){
        scanf("%d %d %d %d",&n,&m,&x,&y);
        x++;
        y++;
        memset(f,0,sizeof(f));
        f[x][y]=1;
        ans=0;
        dfs(x,y);
        printf("%d\n",ans);
    }
    return 0;
}

M - 八皇后问题

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
#include<bits/stdc++.h>
using namespace std;
const int n = 8;
int tmp, ans;
int x[10];
int chess[10][10];
bool no(int r, int c) {//判断两个皇后的坐标是否冲突
	for (int i = 0; i < r; i++) {
		if (x[i] == c || abs(r - i) == abs(c - x[i])) 
		return false;
	}
	return true;
}
void queen(int k) {
	if (k == n) { 
	ans = max(ans, tmp);//找所有情况的八皇后的最大权值和
	return;
	}
	for (int i = 0; i < n; i++) {
		if (no(k, i)) {
			x[k] = i;//dfs前做好标记
			tmp += chess[k][i];
			queen(k + 1);
			x[k] = 0;//dfs后删除标记
			tmp -= chess[k][i];
		}
	}
}
int main() 
{
	int t;
	scanf("%d", &t);
	while (t--) {
		tmp = ans = 0;
		memset(x, 0, sizeof(x));
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++)
				scanf("%d", &chess[i][j]);
		}
		queen(0);
		printf("%d\n", ans);
	}
	return 0;
}

N - 选数

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
#include<bits/stdc++.h>
using namespace std;
int ans,n,k,a[50],i;
bool check(int a)
{
    int i;
    if(a<2)
	return false;
    for(i=2;i<=sqrt(a);i++)
    if(a%i==0)
	return false;
    return true;
}
void dfs(int num,int i,int sum){
    if(num==k){//输入的k个数之和是素数
        if(check(sum))
		++ans;
        return;
    }
    for(i;i<=n;i++)
    dfs(num+1,i+1,sum+a[i]);//向下一个数搜索
}
int main()
{
    cin>>n>>k;
    for(i=1;i<=n;i++)
    cin>>a[i];
    dfs(0,1,0);
    cout<<ans;
    return 0;
}

O - 打开灯泡 Switch the Lamp On

想搞懂的自行了解c++双端队列（deque）的基本操作

搬运的题解：

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;
#define fir(i,a,b) for(int i=a;i<=b;i++)
const int N=510;
const int dxy1[4][2]= {{1,1},{-1,-1},{1,-1},{-1,1}},dxy2[4][2]= {{1,1},{0,0},{1,0},{0,1}};
struct node
{
    int x,y;
};
int t,n,m,ans=1e8,dis[N][N];
char s[N][N];
bool vis[N][N];
deque<node> q;
int check(int x,int y)
{
    return x>=0 && x<=n && y>=0 && y<=m;
}
void bfs()
{
    vis[0][0]=1;
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    q.push_front(node {0,0});
    dis[0][0]=0;
    while(q.size())
    {
        node now=q.front();
        q.pop_front();
        fir(i,0,3)
        {
            int tx=now.x+dxy1[i][0],t1=now.x+dxy2[i][0];
            int ty=now.y+dxy1[i][1],t2=now.y+dxy2[i][1];
            int tt=(s[t1][t2] != (i<=1? '\\':'/'));
            if(check(tx,ty) && dis[tx][ty]>dis[now.x][now.y]+tt)
            {
                dis[tx][ty]=dis[now.x][now.y]+tt;
                if(tt)
                    q.push_back(node {tx,ty});
                else
                    q.push_front(node {tx,ty});
            }
        }
    }
}
int main()
{
        cin>>n>>m;
        fir(i,1,n)
        fir(j,1,m)
        cin>>s[i][j];
        bfs();
        if(dis[n][m]<1e8)
            cout<<dis[n][m]<<endl;
        else
            cout<<"NO SOLUTION"<<endl;
    return 0;
}

可算肝完了。。。