🔥夏日萤火
文章 标签 分类 友链&留言板
🔥夏日萤火

目录

挑战程序设计竞赛第二章第一节习题总结

 收录于 挑战程序设计竞赛
   约 4768 字   预计阅读 10 分钟    次阅读  
本章主要内容
深度优先搜索（DFS），广度优先搜索（BFS）。

深度优先搜索

POJ-1979 Red and Black

原题链接

思路
这道题dfs和bfs都能做，并且在效率上也差不多，总之就是要搜索到每一个能走的黑砖，dfs和bfs都能够搜索到全部情况，所以这道题两种做法都可以。
参考代码

dfs做法

#include <cstdio>
#include <queue>
using namespace std;

const int maxn = 110;
char tiles[maxn][maxn];
int flag[maxn][maxn];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
int res = 1, n, m;

void dfs(int x, int y)
{
    for(int i = 0; i < 4; i++)
    {
    	int tmpX = x+dx[i], tmpY = y+dy[i];
    	if(tmpX >= 0 && tmpX < m && tmpY >= 0 && tmpY < n && tiles[tmpX][tmpY] == '.')
    	{
    		//printf("%d %d\n", x, y);
    		res++;
    		tiles[tmpX][tmpY] = '#';
    		dfs(tmpX, tmpY);
    	}	
    }
}

int main(void)
{
    while(scanf("%d %d", &n, &m) == 2 && n && m)
    {
        getchar();
        res = 1;
        int stX, stY;
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                scanf("%c", &tiles[i][j]);
                if(tiles[i][j] == '@') 
                {
                	stX = i;
                	stY = j;
                }
            }
            getchar();
        }
        dfs(stX, stY);
        printf("%d\n", res);
    }

    return 0;
}

bfs做法

#include <cstdio>
#include <queue>
#include <utility>
#include <cstring>
using namespace std;

typedef pair<int, int> PII;
const int maxn = 110;
queue<PII> NextStep;
char tiles[maxn][maxn];
int flag[maxn][maxn];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
int res = 1, n, m;

void bfs(void)
{
    while(!NextStep.empty())
    {
        PII t = NextStep.front();
        NextStep.pop();
        for(int i = 0; i < 4; i++)
        {
            int x = t.first + dx[i], y = t.second + dy[i];
            if(x >= 0 && x < m && y >= 0 && y < n && tiles[x][y] == '.' && flag[x][y] == 0)
            {
                flag[x][y] = 1;
                res++;
                NextStep.push({x, y});
            }
        }
    }

    printf("%d\n", res);
}

int main(void)
{
    while(scanf("%d %d", &n, &m) == 2 && n && m)
    {
        res = 1;
        getchar();
        memset(flag, 0, sizeof(flag));
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                scanf("%c", &tiles[i][j]);
                if(tiles[i][j] == '@') NextStep.push({i, j});
            }
            getchar();
        }
        bfs();
        NextStep = queue<PII>();
    }

    return 0;
}

Aizu-0118 Property Distribution

原题链接

思路
简单的dfs，注意res的更新，并且这里能合并到一起的地块只能是上下左右相邻的四个地块构成。
参考代码 
#include <cstdio>
using namespace std;

const int maxn = 110;
char field[maxn][maxn];
int n, m, res;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};

void dfs(int x, int y, char species)
{
    int flag = 1;	//标记当前这块地是否被划分完
    for(int i = 0; i < 4; i++)
    {
        int tmpX = x + dx[i], tmpY = y + dy[i];
        if(tmpX >= 0 && tmpX < n && tmpY >= 0 && tmpY < m && field[tmpX][tmpY] == species)
        {
            //printf("%d %d\n", tmpX, tmpY);
            flag = 0;	//相邻的地块中还有同类作物，则继续扩大边界
            field[tmpX][tmpY] = '.';	//标记搜过的地方
            dfs(tmpX, tmpY, species);
            if(flag) return;	//搜完了就结束递归
        }
    }
}

int main(void)
{
    while(scanf("%d %d", &n, &m) == 2 && n && m)
    {
        getchar();
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
                scanf("%c", &field[i][j]);
            getchar();
        }

        res = 0;
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                if(field[i][j] != '.')
                {
                    res++;	//种这类作物的地块可以划分出一块地
                    char tmpSpecies = field[i][j];	//记录当前地块的作物种类
                    field[i][j] = '.';	//标记划分时已经用过的土地
                    dfs(i, j, tmpSpecies);
                }
            }
        }
        printf("%d\n", res);
    }

    return 0;
}

Aizu-0033 Ball

原题链接

思路
dfs，能够按题目条件放置就继续往下一个球递归，若10个球都能按题目条件放置，则结束递归并将标记的flag值变为1，若有一个球不满足条件则提前结束递归并将flag值变为0。
如果不是刻意练习dfs，这道题直接按题意模拟也可以，且实现起来更简单。
参考代码

dfs做法

#include <cstdio>

const int maxn = 20;
int a[maxn];
int TopB, TopC, flag;

void dfs(int idx)
{
	if(idx == 10)
	{
		//若10个球都能搞满足条件地放置完，则flag为1
		flag = 1;
		return ;
	}
	if(a[idx] > TopB)
	{
		TopB = a[idx];
		dfs(idx+1);
	}
	else if(a[idx] > TopC)
	{
		TopC = a[idx];
		dfs(idx+1);
	}
	
	return ;	//若不能满足条件放置则flag值仍为0
}

int main(void)
{
	int T;
	scanf("%d", &T);
	while(T--)
	{
		TopB = 0, TopC = 0, flag = 0;
		for(int i = 0; i < 10; i++) 
			scanf("%d", &a[i]);
		dfs(0);
		if(flag) printf("YES\n");
		else printf("NO\n");
	}

	return 0;
}

模拟做法

#include <cstdio>

int main(void)
{
	int T;
	scanf("%d", &T);
	while(T--)
	{
		int Btop = 0, Ctop = 0, flag = 1;
		for(int i = 0; i < 10; i++)
		{
			int tmp;
			scanf("%d", &tmp);
			if(tmp > Btop) Btop = tmp;
			else if(tmp > Ctop) Ctop = tmp;
			else flag = 0;
		}
		if(flag) printf("YES\n");
		else printf("NO\n");
	}

	return 0;
}

POJ-3009 Curling 2.0

原题链接

思路

dfs。这道题由于方块会消失，感觉bfs不太好写，就用的dfs。

  1. 冰壶可以朝四个方向投掷，但是投掷方向上的第一个位置不可以有方块，否则不能进行投掷。
  2. 运动过程中撞到方块后，注意进行回溯，因为不同的投掷路线可能撞到同一个方块。
  3. 由于dfs不能搜索到最短路，所以需要穷举每种可行的方案，最后比较得到投掷次数最少的方案。
  4. 注意撞到砖块后是停在撞到砖块的前一个位置。
参考代码 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 110;
int mesh[maxn][maxn];
int n, m, res, cnt;
int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};

void dfs(int x, int y, int cnt)
{
    if(cnt > 10) return ;	//投掷次数大于10次的路线不可行，结束递归

    for(int i = 0; i < 4; i++)
    {
        int tmpX = x + dx[i], tmpY = y + dy[i];	//投掷时遇到的第一个相邻方格
        if(mesh[tmpX][tmpY] == 1) continue;	//若该方格为砖块，则被阻挡，不能向该方向投掷
        
        //投掷后的运动过程
        while(mesh[tmpX][tmpY] == 0)	
        {
        	tmpX += dx[i];
        	tmpY += dy[i];
        }
        if(mesh[tmpX][tmpY] == 1)	//运动过程中遇到了砖块
        {
        	mesh[tmpX][tmpY] = 0;	//被撞砖块消失
        	dfs(tmpX-dx[i], tmpY-dy[i], cnt+1);	//进行下一次投掷
        	mesh[tmpX][tmpY] = 1;	//回溯，否则其他投掷路线会发生错误
        }
        else if(mesh[tmpX][tmpY] == -1)	//出界
        	continue ;
        else if(mesh[tmpX][tmpY] == 3)	//能够达到终点，并且看是否为投掷次数更少的路线
        {
        	res = min(res, cnt);
        	return ;
        }
    }
}

int main(void)
{
    while(scanf("%d %d", &n, &m) == 2 && n && m)
    {
        memset(mesh, -1, sizeof(mesh)); //若为-1则出界
        res = 2e9, cnt = 1;
        int stX, stY;
        //从下标1开始读入方便标记出界情况
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                scanf("%d", &mesh[i][j]);
                if(mesh[i][j] == 2)
                {
                    stX = i;
                    stY = j;
                    mesh[i][j] = 0;	//记录了起点位置后可以标记为空
                }
            }
        }

        dfs(stX, stY, cnt);
        if(res <= 10) printf("%d\n", res);
        else printf("-1\n");
    }

    return 0;
}

广度优先搜索

Aizu-0558 Cheese

原题链接

思路
bfs。由于这道题里的路径有重叠，即一个点可能会在最短路中经过不止一次，所以为了保证搜到的仍然是最短路，需要更新起点进行多次bfs，并将每一次bfs的结果相加。这里把每个奶酪的坐标看作一个起点，从S开始一直吃到N号奶酪。
参考代码 
#include <cstdio>
#include <queue>
#include <utility>
#include <cstring>
using namespace std;

const int maxn = 1100;
typedef pair<int, int> PII;
char mesh[maxn][maxn];
int h, w, n;
int dis[maxn][maxn], res, CanEat;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
queue<PII> q;

//由于会从不同起点开始进行多次bfs，初始化也会进行多次，写成函数可以简化代码
void init(int newStartX, int newStartY)
{
	memset(dis, -1, sizeof(dis));
	q = queue<PII>();
    dis[newStartX][newStartY] = 0;
    q.push({newStartX, newStartY});
}

void bfs(int x, int y)
{
    init(x, y);
    CanEat = 1;	//标记当前能够吃的奶酪是几

    while(!q.empty())
    {
    	auto t = q.front();
    	q.pop();
    	for(int i = 0; i < 4; i++)
    	{
    		int tmpX = t.first + dx[i], tmpY = t.second + dy[i];
    		if(tmpX >= 0 && tmpX < h && tmpY >= 0 && tmpY < w 
    		&& mesh[tmpX][tmpY] != 'X' && dis[tmpX][tmpY] == -1)
    		{
    			// printf("%d %d\n", tmpX, tmpY);

    			dis[tmpX][tmpY] = dis[t.first][t.second] + 1;
    			if(mesh[tmpX][tmpY] == CanEat+'0')	//如果是能吃的奶酪则吃掉
    			{
    				// printf("%d\n", CanEat);
    				// printf("%d %d\n", tmpX, tmpY); 
    				
    				CanEat++;
    				mesh[tmpX][tmpY] = '.';	//奶酪吃了就没了
    				res += dis[tmpX][tmpY];
    				if(CanEat == n-'0') return ;	//吃完了则结束搜索
    				init(tmpX, tmpY);
    				break;  //到了奶酪的位置必须要立刻结束这次的搜索，开始新一次的搜索
    			}
    			else	//吃不了的奶酪当做普通路径处理
    				q.push({tmpX, tmpY});
    		}
    	}
    }
}

int main(void)
{
    int stX, stY;
    scanf("%d %d %d", &h, &w, &n);
    for(int i = 0; i < h; i++)
    {
        getchar();
        for(int j = 0; j < w; j++)
        {
            scanf("%c", &mesh[i][j]);
            if(mesh[i][j] == 'S')
            {
                stX = i;
                stY = j;
            }
        }
    }
    bfs(stX, stY);

    printf("%d\n", res);

    return 0;
}

POJ-3669 Meteor Shower

原题链接

思路
bfs。这道题需要注意的是，比较时间时，一定要先加1再比较，否则会出错。
参考代码 
#include <cstdio>
#include <utility>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

typedef pair<int, int> PII;
const int maxn = 500;
const int inf = 0x3f3f3f3f;
queue<PII> q;
int plane[maxn][maxn];	//下标对应位置，元素有值则对应流星砸到的时间
bool st[maxn][maxn];	//标记是否第一次达到
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};

int bfs(int x, int y)
{
    q.push({x, y});
    plane[x][y] = 0;

    while(!q.empty())
    {
        PII t = q.front();
        q.pop();
        for(int i = 0; i < 4; i++)
        {
            int tmpX = t.first + dx[i], tmpY = t.second + dy[i];
            if(tmpX >= 0 && tmpY >= 0)
            {
                if(plane[tmpX][tmpY] == inf)    
                {
                	plane[tmpX][tmpY] = plane[t.first][t.second] + 1;
                	return plane[tmpX][tmpY];
                }
                else if(!st[tmpX][tmpY] && plane[t.first][t.second]+1 < plane[tmpX][tmpY])	//这里判断时间时记得加1再判断
                {
                	st[tmpX][tmpY] = true;
                	plane[tmpX][tmpY] = plane[t.first][t.second] + 1;
                	q.push({tmpX, tmpY});
                }
            }
        }
    }

    return -1;	//如果队列为空还没到达安全地带，说明到不了
}

int main(void)
{
    int M;
    scanf("%d", &M);
    memset(plane, 0x3f, sizeof(plane)); //值全部初始化为inf，后面标记了时刻的就是会被流星砸到的地方，否则就是安全地带
    while(M--)
    {
        int x, y, t;
        scanf("%d %d %d", &x, &y, &t);
        //读入时标记好哪些地方会被流星在什么时刻砸到，注意保留的是最早时刻
        plane[x][y] = min(plane[x][y], t);
        for(int i = 0; i < 4; i++)
        {
            int tx = x + dx[i], ty = y + dy[i];
            if(tx >= 0 && ty >= 0)
                plane[tx][ty] = min(plane[tx][ty], t);
        }
    }
    
    if(plane[0][0] == 0) printf("-1\n"); //在起点就被砸，来不及走
    else printf("%d\n", bfs(0, 0));

    return 0;
}

Aizu-0121 Seven Puzzle

原题链接

思路
bfs。这道题有1000组左右的输入，所以直接每组bfs的话会超时，那么可以从终点进行反向bfs，记录下终状态第一次变换到每种状态所用的变换次数，这个次数就是对应状态变换到终状态的次数，生成一个哈希表。对于每一组数据直接查表就好，这样查表的时间复杂度就是$O(1)$的，效率提升了很多。
另外还需要注意的是这道题的输入方式，以及每次输入后记得初始化储存状态的string。
参考代码 
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <unordered_map>
using namespace std;

string st;
queue<string> q;
unordered_map<string, int> dis;	//储存从终状态变换到所有可能的状态需要多少次
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};

void bfs(void)
{
    string ed = "01234567";
    q.push(ed);
    dis[ed] = 0;

    while(!q.empty())
    {
        auto t = q.front();
        q.pop();

        int disTmp = dis[t];	//储存从终状态到达当前状态的变换次数
        for(int i = 0; i < 4; i++)
        {
            //找到0的位置并转换到二维
            int k = t.find('0');
            int x = (k / 4) + dx[i], y = (k % 4) + dy[i];
            if(x >= 0 && x < 2 && y >= 0 && y < 4)
            {
                swap(t[x * 4 + y], t[k]);
                if(!dis.count(t))	//若是第一次达到该状态，则加入队列
                {
                    dis[t] = disTmp + 1;	//变换后次数加1
                    q.push(t);
                }
                swap(t[x * 4 + y], t[k]);	//复原，会多次达到这个状态并且会利用多次
            }
        }
    }
}

int main(void)
{
    bfs();	//生成终点变化到各状态对应变化次数的哈希表

    int a[8];
    while(scanf("%d", &a[0]) != EOF)
    {
      	//注意记得每次清空
      	st.clear();

      	for(int i = 1; i < 8; i++) scanf("%d", &a[i]);
      	for(int i = 0; i < 8; i++) st += a[i] + '0';
        printf("%d\n", dis[st]);	//直接在哈希表中查找终点变化到该状态变化了多少次
    }

    return 0;
}

穷竭搜索

POJ-2718 Smallest Difference

原题链接

思路
穷竭搜索，可以用库函数或者手写dfs实现。 但更推荐直接用库函数，实现简单并且速度更快。
我自己手写的dfs暴搜（也可能是我水平问题）几乎是贴着题目时限过的，不排除发生意外超时的情况，比较危险。建议还是用库函数。
参考代码

库函数做法

/*237ms*/
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cctype>
using namespace std;

const int maxn = 20;
int a[maxn];

int main(void)
{
	int T;
	scanf("%d", &T);
	getchar();
	while(T--)
	{
		int cnt = 0, res = 2e9;
		char tmp;
		while((tmp = getchar()) != '\n') 
			if(isdigit(tmp))
				a[cnt++] = tmp - '0';

		//恰有两数则直接输出它们的差
		if(cnt == 2) 
		{
			printf("%d\n", abs(a[0]-a[1]));
			continue;
		}
		do
		{
			//不能以0开头
			if(a[0] == 0 || a[cnt/2] == 0) continue;

			//两数位数越接近，则两数的差越小
			int x = 0, y = 0;
			for(int i = 0; i < cnt/2; i++) 
				x = x*10 + a[i];
			for(int i = cnt/2; i < cnt; i++)
				y = y*10 + a[i];
			res = min(res, abs(x-y));
		}
		while(next_permutation(a, a+cnt));
		printf("%d\n", res);
	}

	return 0;
}

dfs做法

/*954ms*/
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 20;
int a[maxn], perm[maxn];
bool st[maxn];
int res, cnt;

void dfs(int idx)
{
    if(idx == cnt)
    {
        /*在这里剪枝仍然会超时
        if(perm[0] == 0 || perm[idx/2] == 0) return ; 
        */

        int x = 0, y = 0;
        for(int i = 0; i < idx / 2; i++)
            x = x * 10 + perm[i];
        for(int i = idx / 2; i < idx; i++)
            y = y * 10 + perm[i];

        res = min(res, abs(x - y));
        return;
    }

    for(int i = 0; i < cnt; i++)
    {
        if(!st[a[i]])
        {
            st[a[i]] = true;
            if(a[i] == 0 && (idx == cnt / 2 || idx == 0)) 
            {
            	st[a[i]] = false;
            	continue;
            }
            perm[idx] = a[i];
            dfs(idx + 1);
            st[a[i]] = false;
        }
    }

}

int main(void)
{
    int T;
    scanf("%d", &T);
    getchar();
    while(T--)
    {

        char tmp;
        cnt = 0, res = 2e9;
        memset(st, 0, sizeof(st));
        while((tmp = getchar()) != '\n')
            if(isdigit(tmp))
                a[cnt++] = tmp - '0';

        if(cnt == 2)
            printf("%d\n", abs(a[0] - a[1]));
        else
        {
            dfs(0);
            printf("%d\n", res);
        }
    }

    return 0;
}

Aizu-0525 Osenbei

原题链接

思路
用dfs进行穷竭搜索。需要注意的是：
翻转问题中，翻转的顺序一般不会影响最终的结果。
这里由于行数比较少且只有两种状态，所以可以先递归找出行翻转的所有可能性。当递归到最后一行时，再去考虑列，0比较多则需要翻转，1比较多则不用翻转。对于列并不需要真的翻转，统计当前列的0和1的数量。比较即可。
这里使用bitset可以简化操作。
参考代码 
#include <iostream>
#include <bitset>
#include <algorithm>
using namespace std;

const int MaxRow = 20, MaxColumn = 10010;
bitset<MaxColumn> b[MaxRow];
int r, c;
int res;

void dfs(int row)
{
    if(row == r)
    {
        int res_tmp = 0;
        for(int i = 0; i < c; i++)
        {
            //统计当前列中1的个数
            int row_tmp = 0;
            for(int j = 0; j < r; j++)
                if(b[j][i]) row_tmp++;

            //选择1多的状态
            res_tmp += max(row_tmp, r-row_tmp);
        }
        res = max(res, res_tmp);

        return ;
    }

    //枚举每行所有可能性
    dfs(row+1);
    b[row].flip();  //翻转当前行
    dfs(row+1);
}

int main(void)
{
    cin.tie(0), cout.tie(0);
    ios::sync_with_stdio(false);

    while(cin >> r >> c && r && c)
    {
        for(int i = 0; i < r; i++)
        {
            int t;
            for(int j = 0; j < c; j++)
            {
                cin >> t;
                b[i][j] = t;
            }
        }

        res = 0;
        dfs(0);
        cout << res << endl;
    }

    return 0;
}

POJ-3050 Hopscotch

原题链接

思路
dfs。穷竭搜索，就是把每一个点都搜完，虽然效率低，但能够搜索到所有可能。这道题必须每一个点都搜到才能得到所有可能序列，所以必须要每个点进行一次深搜。
参考代码 
#include <cstdio>
#include <set>
using namespace std;

const int maxn = 10;
int grid[maxn][maxn];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
set<int> res;

void dfs(int x, int y, int sz, int num)
{
    if(sz == 6)	//得到一个序列就插入set中，利用set特点自动去重
    {
    	res.insert(num);
    	return ;	//结束这次搜索
    }

    for(int i = 0; i < 4; i++)
    {
        int tmpX = x + dx[i], tmpY = y + dy[i];
        if(tmpX >= 0 && tmpX < 5 && tmpY >= 0 && tmpY < 5)
        {
            sz++;
            dfs(tmpX, tmpY, sz, num * 10 + grid[tmpX][tmpY]);
            sz--;	//回溯，进行其他方向的搜索
        }
    }

}

int main(void)
{
    for(int i = 0; i < 5; i++)
        for(int j = 0; j < 5; j++)
            scanf("%d", &grid[i][j]);

    //将每一个点作为起点进行深搜，即可搜索到所有可能的序列
    for(int i = 0; i < 5; i++)
    	for(int j = 0; j < 5; j++)
    		dfs(i, j, 1, grid[i][j]);
    printf("%d\n", res.size());

    return 0;
}

POJ-3187 Backward Digit Sums

原题链接

思路
穷竭搜索。直接按字典序枚举所有最初排列，模拟相加到操作，比较最后加出来的和是不是数据中给的和，如果是，那么输出这个序列。dfs和库函数做法都可以，且效率差不多（当然还是用库函数快一些）但是需要注意的是，这道题的加和操作需要再开一个中间数组来进行，否则会破坏原数组从而影响排列的枚举。
这道题只用找到字典序最小的，所以dfs剪枝后可以达到接近库函数做法的搜索效率。但涉及到枚举数字排列情况的问题还是可以多用库函数。

参考代码

库函数做法

#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 20;
int a[maxn], t[maxn];
int n, sum;

int main(void)
{
    scanf("%d %d", &n, &sum);
    for(int i = 0; i < n; i++) 
    {
        a[i] = i + 1;
        t[i] = a[i];
    }

    do
    {
        //将每次排列后的数组复制到中间数组进行操作，不要打乱原数组
        for(int i = 0; i < n; i++)
            t[i] = a[i];
        
        //模拟相邻两数相加操作
        for(int cnt = n; cnt > 1; cnt--)
            for(int i = 0, j = 1; j < cnt; i++, j++)
                t[i] = t[i] + t[j];

        //由于是按照字典序排列，找到就立刻输出的序列就是字典序最小的序列
        if(t[0] == sum)
        {
            for(int i = 0; i < n; i++) printf("%d ", a[i]);
            printf("\n");
            break;
        }
    }
    while(next_permutation(a, a + n));

    return 0;
}

dfs做法

#include <cstdio>

const int maxn = 10;
int a[maxn], t[maxn];
bool st[maxn];
int n, sum;
int flag;   //标记有没有找到目标序列

void dfs(int idx)
{
    if(idx == n)
    {
        for(int i = 0; i < idx; i++) t[i] = a[i];
        while(idx > 1)
        {    
            for(int i = 0, j = 1; j < idx; i++, j++) t[i] = t[i] + t[j];
            idx--;
        }
        
        if(t[0] == sum)
        {
            for(int i = 0; i < n; i++) printf("%d ", a[i]);
            printf("\n");
            flag = 1;   
        }

        return ;
    }

    for(int i = 1; i <= n; i++)
    {
        if(flag) return ;   //只用找到字典序最小的，找到就结束搜索
        if(!st[i])
        {
            a[idx] = i;
            st[i] = true;
            dfs(idx+1);
            st[i] = false;
        }
    }
}

int main(void)
{
    scanf("%d %d", &n, &sum);

    dfs(0);

    return 0;
}
更新于 2021-02-23
 DFS, BFS, 搜索
返回 | 主页