e971 - 2. 梗圖著色 (Coloring)
題目描述
題目描述了將一張黑白梗圖中，每列成對的兩個黑色像素之間的白色像素塗黑的操作。輸入為一個 m x n 的二維陣列，其中 1 代表黑色，0 代表白色。輸出經過塗色後的陣列。
解題思路
這個問題可以使用貪心演算法解決。對於每一列，從左到右掃描，找到相鄰的兩個黑色像素（1）。然後，將這兩個黑色像素之間的所有白色像素（0）塗黑。重複此過程，直到掃描完所有列。程式碼直接在輸入的陣列上進行修改，避免了額外的空間開銷。使用 getchar_unlocked() 和 putchar_unlocked() 函數可以提高輸入輸出的效率。
複雜度分析
- 時間複雜度: O(m * n^2)。其中 m 是列數，n 是行數。最壞情況下，對於每一列，需要遍歷所有元素以找到相鄰的黑色像素並進行塗色。
- 空間複雜度: O(1)。程式碼直接修改輸入陣列，沒有使用額外的資料結構。
程式碼
#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>
int x,y,i,j,jj;
char a[101][101],b,c='0';
int main(){
scanf("%d%d",&x,&y);
for(;i<x;++i)
for(j=0;j<y;++j)
while(b=getchar_unlocked())
if(b=='0'||b=='1'){
a[i][j]=b;
break;
}
for(i=0;i<x;++i)
for(j=0;j<y;++j)
if(a[i][j]=='1')
for(jj=j+1;jj<y;++jj)
if(a[i][jj]=='1'){
for(;j<jj;++j)
a[i][j]='1';
break;
}
for(i=0;i<x;++i){
for(j=0;j<y;++j){
putchar_unlocked(a[i][j]);
putchar_unlocked(' ');
}
putchar_unlocked('\n');
}
}