紫书搜索 例题7-5 UVA - 129 Krypton Factor

题目链接:

https://vjudge.net/problem/UVA-129

题意:

题解:

代码:

#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MS(a) memset(a,0,sizeof(a)) #define MP make_pair #define PB push_back const int INF = 0x3f3f3f3f; const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ////////////////////////////////////////////////////////////////////////// const int maxn = 1e5+10; int n,m,cnt; int S[maxn]; bool dfs(int cur){ if(cnt++ == n){ for(int i=0; i<cur; i++) { if(i%64==0 && i) printf("\n"); else if(i%4==0 && i) printf(" "); printf("%c",S[i]+'A'); } printf("\n"); printf("%d\n",cur); return 0; } for(int i=0; i<m; i++){ S[cur] = i; int ok = 1; for(int j=1; j*2<=cur+1; j++){ // 为啥是+1？？ 如果不加1 第一个样例： AABAC AB 也就是当cur=1时，就没循环。 int equal = 1; for(int k=0; k<j; k++) if(S[cur-k] != S[cur-k-j]) { equal = 0; break;} if(equal) { ok = 0; break;} } if(ok) if(!dfs(cur+1)) return 0; } return 1; } int main(){ while(scanf("%d%d",&n,&m)){ if(n+m==0) break; cnt = 0; dfs(0); } return 0; }