频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
uva 585 - Triangles(暴力枚举)
2013-12-24 11:43:32         来源:吊炸天的柯小帅  
收藏   我要投稿

题目链接:uva 585 - Triangles


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


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


#include 
#include 
#include 

using namespace std;

const int N = 205;

int n, ans, v[N][N];

void init() {
	char str[N * 2];
	ans = 0;
	memset(v, -1, sizeof(v));

	for (int i = 0; i < n; i++) {
		gets(str);
		int len = strlen(str);
		for (int j = 0; j < len; j++) {
			if (str[j] == '-') v[i][j] = 0;
		}
	}
}

void dfs(int x, int y, int d, int dir) {
	if (x < 0 || x > n) {
		ans = max(ans, d);
		return;
	}

	for (int i = y - d; i <= y + d; i++) {
		if (v[x][i] == -1) {
			ans = max(ans, d);
			return ;
		}
	}

	dfs(x + dir, y, d + 1, dir);
}

void solve() {
	for (int i = 0; i < n; i++) {
		int t = (n - i) * 2 + i - 1;
		for (int j = i; j < t; j++) if (v[i][j] == 0) {
			if ((j + i) % 2)
				dfs(i, j, 0, 1);
			else 
				dfs(i, j, 0, -1);
		}
	}
}

int main() {
	int cas = 1;
	while(scanf("%d%*c", &n) == 1 && n) {
		init();
		solve();
		printf("Triangle #%d\n", cas++);
		printf("The largest triangle area is %d.\n\n", ans * ans);
	}
	return 0;
}


点击复制链接 与好友分享!回本站首页
相关TAG标签 暴力
上一篇:[LeetCode] Permutation Sequence
下一篇:Leetcode Minimum Window Substring
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站