蓝桥杯每日一练-c++喜羊羊与灰太狼（1）

描述

灰太狼历尽千辛万苦，终于抓到了 n 只小羊，他们的编号依次是 1……n。灰太狼和红太狼商量好，今晚先吃掉其中的 m 只羊。但是，关于先吃谁后吃谁的问题，他们产生了争执（灰太狼居然敢于和红太狼产生争执？）。

当然，这个争执的过程并没有什么好看的。作为观众，我们不妨来思考一个问题放松一下：

从 n 只羊中选 m 只羊来吃，有哪些可行的顺序呢？

例如：3 只羊中选 2 只来吃，所有可行的顺序有以下 6 种：

1,2

1,3

2,1

2,3

3,1

3,2

请编写程序，根据输入的 n,m 列出所有可行的顺序。

输入

输入二个整数 n,m。

输出

输出所有可行的顺序，每行一组。

样例

输入

3 2

输出

1 2
1 3
2 1
2 3
3 1
3 2

提示 数据范围

1≤m≤n≤10

这道题可以用暴力枚举来做，但显然……TIME OUT（说起来都是泪啊，为了你们我试了有试），所以要优化一（亿）下。用递归呢？AC!

那是什么递归呢，搜索可以吗，都怎么问了，那肯定是可以的了，那是dfs还是bfs呢？

dfs貌似要好做一些。

代码如下：

#include

using namespace std;

int vis[20];

int ans[20];

int n,m;

void dfs(int t) {

if(t>m) {

for(int i=1; i<=m; i++)

cout<

cout<

return;

}

for(int i=1; i<=n; i++) {

if(vis[i]==0) {

ans[t]=i;

vis[i]=1;

dfs(t+1);

vis[i]=0;

}

}

}

int main() {

cin>>n>>m;

dfs(1);

return 0;

}