DFS 검색 배열 및 조합
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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
이진 트리: 최저 공통 조상(LCA)Leetcode 문제 를 참조할 수 있습니다. 이진 트리가 주어지면 트리에서 주어진 두 노드의 lowest common ancestor(LCA)를 찾으십시오. 입력: root = [3,5,1,6,2,0,8,null,...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.