d534 - 1. 戰艦謎題
題目描述
題目給定一個 2x2 的格子，已知每一列和每一行的總重量。要求找出四個格子的重量，使得每格子的重量為 1, 2, 或 3，且滿足給定的列和行總重量條件。如果沒有解，則輸出 "No solutions."。
解題思路
由於格子的數量很少，且重量只有 1, 2, 3 三種可能，因此可以使用暴力搜尋的方法。程式碼使用四個巢狀迴圈，枚舉所有可能的重量組合。對於每種組合，檢查是否滿足列和行的總重量條件。如果滿足，則輸出該組合並結束搜尋。如果所有組合都檢查完畢，仍然沒有找到解，則輸出 "No solutions."。程式中 aa, bb, cc, dd 分別代表四個格子的重量。ans 變數用於標記是否找到解。
複雜度分析
- 時間複雜度: O(3^4) = O(81)。因為有四個巢狀迴圈，每個迴圈迭代 3 次。
- 空間複雜度: O(1)。程式只使用了幾個整數變數，空間使用量不隨輸入大小變化。
程式碼
#include <iostream>
using namespace std;
int main(){
int a,b,c,d;
while(cin >> a >> b >> c >> d){
bool ans=0;
for(int aa=0;aa<=3&&ans!=1;aa++){
for(int bb=0;bb<=3&&ans!=1;bb++){
for(int cc=0;cc<=3&&ans!=1;cc++){
for(int dd=0;dd<=3&&ans!=1;dd++){
if(aa==bb||bb==cc||cc==dd||aa==cc||aa==dd||bb==dd)
continue;
if(aa+bb==a&&cc+dd==b&&aa+cc==c&&bb+dd==d){
cout << aa << " " << bb << "\n" << cc << " " << dd << "\n";
ans=1;
}
}
}
}
}
if(ans==0)
cout << "No solutions.\n";
}
}