【南理oj】19 - 擅长排列的小明（dfs）

FishWang

发布于 2025-08-26 19:33:21

2320

点击打开题目

擅长排列的小明

时间限制： 1000 ms | 内存限制： 65535 KB

难度： 4

描述小明十分聪明，而且十分擅长排列计算。比如给小明一个数字5，他能立刻给出1-5按字典序的全排列，如果你想为难他，在这5个数字中选出几个数字让他继续全排列，那么你就错了，他同样的很擅长。现在需要你写一个程序来验证擅长排列的小明到底对不对。

输入第一行输入整数N（1<N<10）表示多少组测试数据，每组测试数据第一行两个整数 n m (1<n<9,0<m<=n) 输出在1-n中选取m个字符进行全排列，按字典序全部输出,每种排列占一行，每组数据间不需分界。如样例样例输入

2
3 1
4 2

样例输出

来源 [hzyqazasdf]原创上传者 hzyqazasdf

刚开始没仔细看样例，以为还要用全排列的函数。实际上一个dfs直接过了。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int num[22];
int n,m;
void dfs(int x,int y)
{
	if (x > n)		//全部搜索完
		return;
	if (y == m)		//搜索成功则输出一组 
	{
		for (int i = 1 ; i <= m ; i++)
			printf ("%d",num[i]);
		printf ("\n");
	}
	for (int i = 1 ; i <= n ; i++)
	{
		bool flag = true;
		for (int j = 1 ; j <= y ; j++)
		{
			if (i == num[j])
			{
				flag = false;
				break;
			}
		}
		if (flag)
		{
			num[y+1] = i;
			dfs(i,y+1);
		}
	}
}
int main()
{
	int u;
	scanf ("%d",&u);
	while (u--)
	{
		scanf ("%d %d",&n,&m);
		for (int i = 1 ; i <= n ; i++)
		{
			num[1] = i;
			dfs(i,1);
		}
	}
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-08-26，如有侵权请联系 cloudcommunity@tencent.com 删除

int