TOJ 114
題目
https://toj.tfcis.org/oj/pro/114/
給一個 $n \times m$ 的陣列,如果其中有連續三個相同的連續元素在同一行或列上,輸出 Yes ,否則輸出 No
想法
分別檢查列以及行是否有相同元素即可
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
| #include<iostream> using namespace std; int main(){ int arr[5][6]; for(int i=0 ; i<5 ; i++){ for(int j=0 ; j<6 ; j++){ cin>>arr[i][j]; } } bool find_ans=false; for(int i=0,cnt=1 ; i<5 ; i++,cnt=1){ for(int j=1 ; j<6 && !find_ans ; j++){ if(arr[i][j] == arr[i][j-1]) cnt++; else cnt=1; if(cnt==3) find_ans=true; } } for(int j=0,cnt=1 ; j<6 ; j++,cnt=1){ for(int i=1 ; i<5 && !find_ans ; i++){ if(arr[i][j] == arr[i-1][j]) cnt++; else cnt=1; if(cnt==3) find_ans=true; } } if(find_ans) cout<<"Yes\n"; else cout<<"No\n";
return 0; }
|
複雜度分析
總時間複雜度約為 $O(3nm)$