DFS 검색 배열 및 조합

DFS 를 사용 하여 12 이내 의 다섯 자리 숫자 를 검색 하 는 연습 을 합 니 다. 예 를 들 어

1 2 3 4 5
1 2 3 4 6
...
...
...
12 11 10 9 7
12 11 10 9 8

수학 배열 과 조합 방법 을 이용 하여 알 수 있 는 결 과 는 12*11*10*9*8 = 95040 이다.
주로 하나의 배열 로 방문 상 태 를 기록 하고 하나의 solve () 함 수 를 이용 하여 검색 결 과 를 저장 합 니 다. 중간 에 작은 구덩이 가 많 으 니 천천히 밟 고 본인 의 슬 래 그 코드 를 첨부 합 니 다.
이것 도 for 순환 초기 상 태 를 사용 하지 않 아 도 됩 니 다. main 함 수 는 DFS 를 직접 사용 하면 됩 니 다. 더욱 간결 하지만 바둑판 을 옮 겨 다 니 는 것 은 순환 초기 상태 가 좋 습 니 다.두 번 째 는 후기 간결 판 DFS 코드 다.（2017/3/25）

#include 

using namespace std;

int num[5] = { 0 };     //       
bool idx[13] = { false };       //       
int count = 0;

void solve()
{
    for (int i = 0; i < 5; i++)
    {
        cout << num[i] << " ";
    }
    count++;
    cout << endl;
}

void dfs(int i, int k)
{
    if (i <= 0 || i >= 13)      //    
    {
        return;
    }

    idx[i] = true;      //        true
    num[k - 1] = i;

    if (k == 5)     //    
    {
        solve();
        return;
    }

    for (int x = 1; x <= 12; x++)
    {
        if (idx[x] == false)
        {
            idx[x] = true;
            dfs(x, k + 1);
            idx[x] = false;
        }
    }
}

int main()
{
    for (int i = 1; i <= 12; i++)
    {
            dfs(i, 1);
            idx[i] = false;    //       ，           ，                   
    }
    cout << "count: " << count << endl;

    return 0;
}

//     DFS  
#include 
#include 
#include 
#include 
#include 

using namespace std;

int n, m;
int num[10];
bool idx[10];

void dfs(int n_, int m_)
{
    if (m_ == m)
    {
        for(int i=0; icout<return;
    }
    for (int x = 0; x <= n; x++)
    {
        if (idx[x] == false)
        {
            idx[x] = true;
            num[m_] = x;
            dfs(x, m_ + 1);
            idx[x] = false;
        }
    }
}
void init()
{
    for (int i = 1; i <= n; i++)
        idx[i] = false;
}
int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    while (~scanf("%d%d", &n, &m) && (m || n))
    {
        init();
        dfs(n, 0);
    }
    return 0;
}

검색 조합의 DFS

#include 
#include 
#include 
#include 
#include 

using namespace std;

int n, m;
int number[10];

void dfs(int pos, int num)
{
    if (num == m)
    {
        for (int i = 0; i < m; i++)
            cout << number[i] << " ";
        cout << endl;
    }
    for (int k = pos; k <= n; k++)
    {
        number[num] = k;
        dfs(k + 1, num + 1);
    }
}
void init()
{
    memset(number, 0, sizeof(number));
}
int main()
{
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    while (~scanf("%d%d", &n, &m) && (m || n))
    {
        init();
        dfs(1, 0);
    }
    return 0;
}