CPE 一顆星選集 49 道必考題
題目連結:https://zerojudge.tw/ShowProblem?problemid=e575
內容
給定一個字元矩形及中心點座標，找出以此座標當中心所對應的最大正方形邊長。
輸入第一列 T (T < 21)代表測資數，每組測資第一列包含矩形高度 M，寬度 N(1 <= M, N <= 100)，詢問數量 Q (Q < 21)，接著有 Q 列中心點座標。
範例輸入
1
7 10 4
abbbaaaaaa
abbbaaaaaa
abbbaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaccaaaaaa
aaccaaaaaa
1 2
2 4
4 6
5 2
範例輸出
7 10 4
3
1
5
1
想法
將矩形內每一點都視為正方形的右下角座標，發現以該點為右下角座標所構成的最大正方形邊長，取決於其左、上、左上這三點構成之正方形最大邊長的最小值 + 1，即可建一個陣列儲存。
因輸入為中心點座標，而陣列儲存數值為右下角，因此需不斷向陣列右下角查詢，直到其值無法再更大。
參考資料:YUI HUANG 演算法學習筆記
程式碼
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
42
43
| #include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false), cin.tie(nullptr)
using namespace std;
int main(){
fastio;
int T, m, n, q, dp[101][101];
char mp[101][101];
cin >> T;
while(T--){
cin >> m >> n >> q;
for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j){
cin >> mp[i][j];
}
}
for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j){
if(i == 0 || j == 0) dp[i][j] = 1;
else if(mp[i][j] == mp[i-1][j-1] && mp[i][j] == mp[i-1][j] && mp[i][j] == mp[i][j-1]){
dp[i][j] = min({dp[i-1][j-1], dp[i-1][j], dp[i][j-1]}) + 1;
}
else dp[i][j] = 1;
}
}
int y, x, ans;
cout << m << " " << n << " " << q << "\n";
while(q--){
cin >> y >> x;
ans = 1;
++y, ++x;
while(y < m && x < n){
if(dp[y][x] >= ans+2){
ans += 2;
++y, ++x;
}
else break;
}
cout << ans << "\n";
}
}
return 0;
}
|