d914 - 2. 圍棋資料庫比對
題目描述
題目要求計算兩個圍棋棋盤的相異程度。相異程度的計算方式是：如果一個棋盤在某個座標有棋子，而另一個棋盤沒有，則相異程度加 1；如果一個棋盤是黑子，另一個棋盤是白子，則相異程度加 2。
解題思路
本題可以使用二維陣列來模擬棋盤。a1 和 a2 分別代表兩個棋盤。陣列中的值表示棋子的顏色，0 表示沒有棋子，1 表示黑子，2 表示白子。
首先，讀取兩個棋盤的棋子資訊，並將其記錄在 a1 和 a2 陣列中。然後，遍歷棋盤的每個座標，比較兩個棋盤在該座標上的棋子情況，並根據題目描述計算相異程度。
複雜度分析
- 時間複雜度: O(n + m + 21 * 21)，其中 n 和 m 分別是兩個棋盤的棋子數量。由於棋盤大小固定為 21x21，因此時間複雜度可以簡化為 O(n + m)。
- 空間複雜度: O(21 * 21)，即 O(1)，因為棋盤大小固定。
程式碼
#include <iostream>
using namespace std;
int a1[21][21],a2[21][21],n,x,y,b,ans;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n;
while(n--){
cin >> x >> y >> b;
a1[x][y]=b+1;
}
cin >> n;
while(n--){
cin >> x >> y >> b;
a2[x][y]=b+1;
}
for(int i=0;i<21;++i){
for(int j=0;j<21;++j){
if(a1[i][j]+a2[i][j]==3){
ans+=2;
}
else if((a1[i][j]&&!a2[i][j])||(!a1[i][j]&&a2[i][j])){
++ans;
}
}
}
cout << ans;
}