题目简介
- 题源：1079 - 寻找X | CCUT OJ
- 题意：给定仅包含
*和.的二维矩阵，寻找由*所组成的最大的X形的臂长。 - 数据范围：\(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;
}