e787 - b2.尋寶地圖(Map)
題目描述
題目描述了阿昂尋找特級廚具的過程。他得到了一張藏寶圖，但圖上標示的 1 並非都是寶藏所在地。一位老人給了他一張轉換圖，如果藏寶圖在轉換圖的同一列或同一行的總和為奇數，則藏寶圖上的標示需要轉換（0 變 1，1 變 0）。要求輸出轉換後的藏寶圖。
解題思路
這題的核心思想是根據轉換圖來修改原始藏寶圖。對於藏寶圖中的每個位置 (i, j)，我們需要計算轉換圖中第 i 列和第 j 行的元素之和。如果該和為奇數，則將藏寶圖中 (i, j) 的值進行翻轉（0 變 1，1 變 0）。
具體步驟如下：
- 讀取藏寶圖和轉換圖的尺寸 (N 和 M)。
- 讀取藏寶圖和轉換圖的數據。
- 創建一個新的地圖
c，用於存儲轉換後的藏寶圖。 - 對於藏寶圖中的每個位置 (i, j)，計算轉換圖中第 i 列和第 j 行的元素之和。
- 如果該和為奇數，則將
c[i][j]設置為原始藏寶圖中 (i, j) 的值的反轉。 - 輸出轉換後的藏寶圖。
複雜度分析
- 時間複雜度: O(N^2 * (N + M))。讀取地圖需要 O(N * M) 的時間。計算每一格的轉換需要遍歷 N 列和 M 行，因此總時間複雜度為 O(N * M * (N + M))。在最壞情況下，N 和 M 的值接近，因此可以簡化為 O(N^2 * (N + M))。
- 空間複雜度: O(N * M)。需要額外的空間來存儲轉換後的藏寶圖
c。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
char a[101][101],b[101][101],c[101][101],x,y,i,j;
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
int main(){
x=read();
y=read();
for(i=0;i<x;++i){
for(j=0;j<y;++j){
while(b[i][j]<47)
b[i][j]=getchar_unlocked();
b[i][j]&=1;
}
}
for(i=0;i<x;++i){
for(j=0;j<y;++j){
while(a[i][j]<47)
a[i][j]=getchar_unlocked();
a[i][j]&=1;
}
}
for(i=0;i<x;++i){
for(j=0;j<y;++j){
for(int ii=0;ii<x;++ii)
c[i][j]+=a[ii][j];
for(int jj=0;jj<y;++jj)
c[i][j]+=a[i][jj];
c[i][j]-=a[i][j];
}
}
for(i=0;i<x;++i){
for(j=0;j<y;++j){
(c[i][j]&1)?putchar_unlocked(!b[i][j]+'0'):putchar_unlocked(b[i][j]+'0');
putchar_unlocked(' ');
}
printf("\n");
}
}