题目分析

题目要求在一个由#（黑色）和-（白色）组成的三角形结构中，找出由白色区域构成的最大三角形区域的大小。输入给出多个三角形结构，每个三角形的高度为n（1 ≤ n ≤ 100），每行的字符数为奇数且从2n-1递减到1。我们需要对每个三角形输出其编号及最大白色三角形区域的面积。

解题思路

1. 输入处理：读取每个三角形的行数n及每行的字符，注意处理前导空格。
2. 深度优先搜索（DFS）：使用DFS来遍历每个可能的白色三角形顶点，计算其能构成的最大三角形大小。
   • 对于朝下的三角形顶点，向上扩展检查是否能构成更大的三角形。
   • 对于朝上的三角形顶点，向下扩展检查是否能构成更大的三角形。
3. 结果计算：记录并更新最大三角形的面积（边长为k的三角形面积为k²）。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int largestTriangle(const vector<string>& triangle) {
    int n = triangle.size();
    int max_area = 0;
    
    // 检查所有可能的三角形
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < triangle[i].size(); ++j) {
            if (triangle[i][j] == '-') {
                // 检查以(i,j)为顶点的最大三角形
                int size = 1;
                bool valid = true;
                while (valid) {
                    if (i + size >= n || j + 2*size >= triangle[i+size].size()) {
                        break;
                    }
                    for (int k = 0; k <= 2*size; ++k) {
                        if (triangle[i+size][j+k] != '-') {
                            valid = false;
                            break;
                        }
                    }
                    if (valid) {
                        size++;
                    }
                }
                max_area = max(max_area, size*size);
            }
        }
    }
    
    return max_area;
}

int main() {
    int case_num = 1;
    while (true) {
        int n;
        cin >> n;
        if (n == 0) break;
        
        vector<string> triangle(n);
        cin.ignore(); // 忽略换行符
        for (int i = 0; i < n; ++i) {
            getline(cin, triangle[i]);
        }
        
        int area = largestTriangle(triangle);
        
        cout << "Triangle #" << case_num << endl;
        cout << "The largest triangle area is " << area << "." << endl;
        cout << endl;
        
        case_num++;
    }
    return 0;
}