題目簡介

• 題源：1079 - 尋找X | CCUT OJ
• 題意：給定僅包含 * 和 . 的二維矩陣，尋找由 * 所組成的最大的X形的臂長。
• 數(shù)據(jù)范圍：\(1\le n,m\le 100\)

題解

想法非常簡單，遍歷整個矩陣，將每個點都是為X的可能中心向四周擴散即可。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    while (cin >> n >> m) {
        vector<string> mapp(n);
        for (int i = 0; i < n; i++) cin >> mapp[i];
        int maxr = 0; // 最大半徑
        for (int i = 0; i < n; i++) { // 將每點都視為可能中心進行擴散
            for (int j = 0; j < m; j++) {
                if (mapp[i][j] == '.') continue;
                int nowr = 0;
                while (1) {
                    int nextr = nowr + 1;
                    bool ok = (i - nextr >= 0) && (i + nextr < n) && (j - nextr >= 0) && (j + nextr < m);
                    if (!ok) break;
                    if (mapp[i - nextr][j - nextr] == '*' && mapp[i - nextr][j + nextr] == '*' && mapp[i + nextr][j - nextr] == '*' && mapp[i + nextr][j + nextr] == '*') // 不包含原點的半徑
                       nowr = nextr;
                    else break;
                }
                maxr = max(maxr, nowr);
            }
        }
        int ans = 2 * maxr + 1; // 將原點加回
        ans == 1 ? cout << 0 << endl : cout << ans << endl;
    }
    return 0;
}