题目链接:uva 10593 - Kites
题目大意:给出一个n*n的图,表示一张纸板,问有多少种方法做成风筝,风筝必须是正方形或者是菱形,并且不能有洞。
解题思路:分正方形和菱形两种情况讨论:
-
正方形,dp[i][j]表示以i,j为右下角的正方形
dp[i][j]=min(dp[i−1][j],dp[i][j−1])
并且如果黄色部分也为'x'的话,dp[i][j]++
-
菱形,dp[i][j]表示菱形的正下角
同样地市黄色部分如果为’x'的话,dp[i][j]++
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 505;
int n, dp[N][N];
char g[N][N];
int solve () {
int ans = 0;
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (g[i][j] == 'x') {
int tmp = min(dp[i-1][j], dp[i][j-1]);
dp[i][j] = tmp + (g[i-tmp][j-tmp] == 'x');
if (dp[i][j] > 1)
ans += dp[i][j] - 1;
}
}
}
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (g[i][j] == 'x') {
int tmp = min(dp[i-1][j-1], dp[i-1][j+1]);
if (tmp == 0 || g[i-1][j] != 'x')
dp[i][j] = 1;
else if (g[i-tmp*2][j] == 'x' && g[i-tmp*2+1][j] == 'x')
dp[i][j] = tmp + 1;
else
dp[i][j] = tmp;
if (dp[i][j] > 1)
ans += dp[i][j] - 1;
}
}
}
return ans;
}
int main () {
while (scanf("%d%*c", &n) == 1 && n) {
for (int i = 1; i <= n; i++)
gets(g[i]+1);
printf("%d\n", solve());
}
return 0;
}
分享到:
相关推荐
We-fly-kites-in-spring.教学设计说明.doc
《We-fly-kites-in-spring》教后感.doc
We-fly-kites-in-spring学习课程.pptx
教案:We-fly-kites-in-spring.
We-fly-kites-in-spring.学习课程.pptx
(完整word)教案:We-fly-kites-in-spring..doc
(完整word版)We-fly-kites-in-spring公开课教案.doc
Unit 3 Lesson 18 Three Kites in the Sky练习题及答案.doc
$ npm install -g @kites/cli # init a project kites init my-project # move to project workspace cd my-project # install dependencies npm install # start development npm start 要更改环境,请使用cmd set...
How many kites are therePPT教案.pptx
Fly loving kites主题放风筝活动策划书.doc
2015春三年级英语下册 Module 7 Unit 1 We fly kites in spring教案 外研版(三起)
风筝-乔里 风筝购物车的管理应用程序
风筝-雅思敏 风筝购物车的客户端应用程序
kites3006.github.io 自我网站
马卡尼Makani是一个开发商用规模的机载风力涡轮机的项目,最终在挪威沿海进行了Makani M600的飞行测试。 现在,所有Makani软件都已开源。 该存储库包含有效的Makani飞行模拟器,控制器(自动驾驶仪),可视化器和...
最新版本winrar510,完美支持64位
4.Five red cats are flying ten yellow kites. 5.Ann and Andy’s wedding anniversary is in April. 6.How many cans can a canner (罐头刀)can if a canner can can cans? Central Vowels 7.Some early birds ...
What to do there They will 15 and fly kites there. They will have a picnic there. 13. A. bus stop B. park gate C. school gate 14. A. By bike B. By bus C. On foot 15. A. go swimming B. ...
win7gpt格式分区设置,轻松解决4 t硬盘装机