f513 - 舉旗遊戲 (Flag)
題目描述
題目給定一個 m x n 的矩陣，矩陣中的每個元素都是 0 或 1。目標是計算矩陣中滿足特定條件的元素的數量。一個元素滿足條件，當且僅當其四個方向的相鄰元素（上、下、左、右）的值都與其自身的值相同。如果元素位於矩陣邊緣，則不存在的相鄰元素不影響判斷。
解題思路
這題的解題思路是遍歷矩陣中的每個元素，並檢查該元素是否滿足題目描述的條件。對於每個元素，我們檢查其上下左右四個相鄰元素的值是否與其自身的值相同。如果所有相鄰元素的值都相同，則將計數器加一。最後，輸出計數器的值。
複雜度分析
- 時間複雜度: O(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 m,n,a[101][101],ans;
inline int judge(int i,int j,int v){
if(i<0||j<0||i>=m||j>=n||a[i][j]!=v)return 1;
return 0;
}
inline int check(int i,int j){
for(int ii=-1;ii<=1;++ii)
for(int jj=-1;jj<=1;++jj)
if(judge(i+ii,j+jj,a[i][j])==0&&(ii!=0||jj!=0))
return 0;
return 1;
}
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(int x) {
if(x==0)
putchar_unlocked('0');
else{
int stk[9],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
}
int main(){
m=read();
n=read();
for(int i=0;i<m;++i)
for(int j=0;j<n;++j)
a[i][j]=read();
for(int i=0;i<m;++i)
for(int j=0;j<n;++j)
if(check(i,j))
++ans;
write(ans);
}