uva129 - Krypton Factor 7.4.3 어려운 꼬치

11296 단어 uva

7.4.3 어려운 꼬치
학습점: dfs에 반환값을 추가하고 귀속 검색 과정에서 성공하면 바로 종료합니다
//7.4.3  
#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int n,L;
int cnt;
char v[81];

bool judge(int cur)
{
    for(int i=1;i<=(cur+1)/2;i++)// 2*i 
    {
        bool equal=1;
        for(int j=0;j<i;j++)
            if(v[cur-i-j]!=v[cur-j])  
            {
                equal=0;
                break;
            }
        if(equal)
            return false;
    }
    return true;
}

int dfs(int cur)
{
    //printf("cur: %d
", cur);
for(int i=0;i<L;i++) { v[cur]='A'+i; if(judge(cur)) { cnt++; if(cnt==n) { v[cur+1]=0; printf("%s
", v); return 1; } if(dfs(cur+1)) return 1; } } return 0; } int main() { while(cin>>n>>L) { cnt=0; dfs(0); } return 0; }

출력 형식을 수정하면 uva129를 해결할 수 있습니다
//7.4.3  
#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int n,L;
int cnt;
char v[81];

bool judge(int cur)
{
    for(int i=1;i<=(cur+1)/2;i++)// 2*i 
    {
        bool equal=1;
        for(int j=0;j<i;j++)
            if(v[cur-i-j]!=v[cur-j])  
            {
                equal=0;
                break;
            }
        if(equal)
            return false;
    }
    return true;
}

void output(int cur)
{
    for(int i=0;i<=cur;i++)
    {
        if(i%4==0 && i>0)
        {
            if(i%64==0 && i>0)
                putchar('
'); else putchar(' '); } putchar(v[i]); } printf("
%d
", cur+1); } int dfs(int cur) { //printf("cur: %d
", cur);
for(int i=0;i<L;i++) { v[cur]='A'+i; if(judge(cur)) { cnt++; if(cnt==n) { v[cur+1]=0; //printf("%s
", v);
output(cur); return 1; } if(dfs(cur+1)) return 1; } } return 0; } int main() { while(cin>>n>>L && n && L) { cnt=0; dfs(0); } return 0; }

좋은 웹페이지 즐겨찾기