題目連結: https://tioj.ck.tp.edu.tw/problems/1035
# 內容
所謂的數獨就是在一個九乘九的宮格（9 個三乘三宮格）裡，填入 1 到 9 等 9 個數字，讓每個數字在每一行、列及所在的三乘三宮格裡都只出現一次。謎題中會預先填入若干數字，其他宮格位則留白讓玩家自行填入，通常數獨題目都會設計成唯一解。但本題之測試輸入可能會有多解，請你通通將其輸出。
你可以假設題目所給的數獨都是合法的，也就是不會有本身已經填好的數字不合規則的情形存在。題目的解數不會超過 50 組。
# 思路
按照題意 DFS 窮舉就有答案囉～～
# 程式碼
#include <bits/stdc++.h> | |
using namespace std; | |
#define N 50000 | |
char str1[N+5] ,str2[N+5]; | |
int lens1, lens2; | |
int main(){ | |
int ans=0; | |
gets(str1); lens1=strlen(str1); | |
gets(str2); lens2=strlen(str2); | |
for(int i=0;i<lens2;i++){ | |
int cnt=0; | |
for(int j=0;j+i<lens1;j++) | |
if(str1[j+i]==str2[j]) cnt++; | |
ans=max(ans,cnt); | |
} | |
for(int i=0;i<lens1;i++){ | |
int cnt=0; | |
for(int j=0;j+i<lens2;j++) | |
if(str2[j+i]==str1[j]) cnt++; | |
ans=max(ans,cnt); | |
} | |
printf("%d",ans); | |
return 0; | |
} |
