f680 - 色塊數量
題目描述
題目要求計算一張 NxN 的圖片中不同色塊的數量。色塊的定義是相鄰（上下左右）且顏色相同的格子。顏色編號為 0 的格子表示白色，不屬於任何色塊。
解題思路
使用深度優先搜尋 (DFS) 演算法來遍歷圖片，找出所有相連的同色塊。對於每個未訪問的彩色格子，啟動一次 DFS，將其及其所有相鄰的同色格子標記為已訪問。每次啟動 DFS 都代表發現了一個新的色塊，因此統計 DFS 啟動的次數即可得到色塊的總數。
複雜度分析
- 時間複雜度: O(N^2)，其中 N 是圖片的尺寸。因為需要遍歷整個 N x N 的圖片，並且 DFS 最多訪問每個格子一次。
- 空間複雜度: O(N^2)，主要來自於遞迴調用的堆疊空間。在最壞的情況下，整個圖片都是同一個顏色，DFS 的深度可能達到 N^2。
程式碼
#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[11][11],n,ans,t;
inline void write(int x) {
if(x==0)
putchar_unlocked('0');
else{
int stk[2],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
}
inline void dfs(int x,int y,int c){
if(x<0||y<0||x>=n||y>=n||a[x][y]!=c)return;
a[x][y]=0;
dfs(x-1,y,c);
dfs(x+1,y,c);
dfs(x,y+1,c);
dfs(x,y-1,c);
}
int main(){
n=getchar_unlocked()-48;
t=getchar_unlocked();
if(t=='0'){
n=10;
getchar_unlocked();
}
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
a[i][j]=getchar_unlocked()-48;
getchar_unlocked();
}
}
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
if(a[i][j]){
++ans;
dfs(i,j,a[i][j]);
}
}
}
write(ans);
}