首页 > 其他 > 详细

UVA - 585 Triangles

时间:2015-05-03 19:00:58      阅读:84      评论:0      收藏:0      [点我收藏+]


题目大意:给出一个倒三角,由若干个小三角形组成,有些三角形为涂上颜色的,问说最大能找出最大的三角形面积。

解题思路:枚举每个没有上色的三角形,向一个方向枚举层数,注意坐标为奇数的只能往下,偶数只能往上。


#include <cstdio>

char grid[105][205];
int n, change, ans;

void DFS(int cur, int x, int y) {
    if (x < 0 || x >= n || y < x || y >= 2 * n - 1 - x || 2 * n - 1 - x < y + 2 * cur - 1)
        return;

    for (int i = y; i < y + 2 * cur - 1; i++)
        if (grid[x][i] != ‘-‘) 
            return;

    if (cur > ans)
        ans = cur;

    DFS(cur + 1, x + change, y - 1);
}

int main() {
    int T = 0;
    while (scanf("%d\n", &n), n) {
        for (int i = 0; i < n; i++)
            gets(grid[i]);

        ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = i; j < 2 * n - 1 - i; j++)
                if (grid[i][j] == ‘-‘) {
                    change = (j - i) % 2 ? 1 : -1;
                    DFS(1, i, j);
                }

        printf("Triangle #%d\nThe largest triangle area is %d.\n\n", ++T, ans * ans);
    }
    return 0;

UVA - 585 Triangles

原文:http://blog.csdn.net/kl28978113/article/details/45460545

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!