牛客小白月赛86(D剪纸游戏)

2024-03-20 17:36

本文主要是介绍牛客小白月赛86(D剪纸游戏),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接:D-剪纸游戏_牛客小白月赛86 (nowcoder.com)

题目描述:

输入描述:

输入第一行包含两个空格分隔的整数分别代表 n 和 m。

接下来输入 n行,每行包含 m 个字符,代表残缺纸张。

保证:
1≤n,m≤10001 

字符仅有 '.' 和 '*' 两种字符,其中 '.' 代表被剪去的部分,'*' 代表未被剪去的部分。

实例:

4 10
*.*.*...**
...***.*..
.**..*.*..
*..*****..

输出:

4

案例解释:

分析:

先用dfs或者是bfs探索每一个区域, 看看这个区域里面的时候可以构成一个长方形

注意: 长方形可能是斜着的, 这个是易错点,比如:

判断正方形:

先求出这一组数据的最左上角(x1, y1) 以及右下角(x2, y2) 统计这个区域里面的个数 num 是否等于(x2 - x1 + 1) * (y2 - y1 + 1); 其实在dfs的时候 就可以进行统计, 引入一个全局变量 x1和y1与当前的dfs遍历的(x, y) x1 = min(x1, x) y1 = min(y1, y) 同理 x2 = max(x2, x) y2 = max(y2, y)

代码:

#include<bits/stdc++.h>
#define y1 Y1
#define fi first
#define endl "\n"
#define se second
#define PI acos(-1)
#define int long long
#define pb(x) push_back(x)
#define PII pair<int, int>
#define Yes cout << "Yes\n";
#define No cout << "No\n";
#define YES cout << "YES\n";
#define NO cout << "NO\n";
#define _for(i, a, b) for(int i = a; i <= b; ++i)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;const int N = 1010;char a[N][N];
bool st[N][N];
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int n, m, num = 0;int cs = 0, ans = 0;
string s;
//bfs的题目
//dfs也可以
int zsX, zsY, yxX, yxY;bool check(int x, int y) {return x >= 1 && x <= n && y >= 1 && y <= m && !st[x][y] && a[x][y] == '.';
}void dfs(int x, int y) {st[x][y] = true;zsX = min(zsX, x);zsY = min(zsY, y);yxX = max(yxX, x);yxY = max(yxY, y);for(int i = 0; i < 4; ++ i ) {int dx = x + dir[i][0];int dy = y + dir[i][1];if(check(dx, dy)) {num ++ ;st[dx][dy] = 1;dfs(dx, dy);}}
}void bfs(int x, int y) {queue<PII> q;q.push({x, y});while(q.size()) {auto p = q.front();q.pop();for(int i = 0; i < 4; ++ i ) {int dx = p.fi + dir[i][0];int dy = p.se + dir[i][1];if(check(dx, dy)) {st[dx][dy] = 1;q.push({dx, dy});}}}
}signed main() {IOS;cin >> n >> m;_for(i, 1, n) {_for(j, 1, m) {cin >> a[i][j];}}_for(i, 1, n) {_for(j, 1, m) {if(check(i, j)) {//	cout << "i = " << i << " j = " << j << endl;num = 1;zsX = 1010; //最左边的 zsY = 1010;yxX = 0;yxY = 0; // 最右边的 st[i][j] = true;dfs(i, j);
//				cout << "num = " << num << endl;
//				cout << "zsX = " << zsX << " zsY = " << zsY << " yxX = " << yxX << " yxY = " << yxY << endl; if(num == (yxX - zsX + 1) * (yxY - zsY + 1)) {ans ++ ; }}}}cout << ans << endl;return 0;
}

这篇关于牛客小白月赛86(D剪纸游戏)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/830233

相关文章

国产游戏崛起:技术革新与文化自信的双重推动

近年来,国产游戏行业发展迅猛,技术水平和作品质量均得到了显著提升。特别是以《黑神话:悟空》为代表的一系列优秀作品,成功打破了过去中国游戏市场以手游和网游为主的局限,向全球玩家展示了中国在单机游戏领域的实力与潜力。随着中国开发者在画面渲染、物理引擎、AI 技术和服务器架构等方面取得了显著进展,国产游戏正逐步赢得国际市场的认可。然而,面对全球游戏行业的激烈竞争,国产游戏技术依然面临诸多挑战,未来的

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

火柴游戏java版

代码 /*** 火柴游戏* <p>* <li>有24根火柴</li>* <li>组成 A + B = C 等式</li>* <li>总共有多少种适合方式?</li>* <br>* <h>分析:</h>* <li>除去"+"、"="四根,最多可用火柴根数20根。</li>* <li>全部用两根组合成"1",最大数值为1111。使用枚举法,A和B范围在0~1111,C为A+B。判断</li>** @

国产游戏行业的崛起与挑战:技术创新引领未来

国产游戏行业的崛起与挑战:技术创新引领未来 近年来,国产游戏行业蓬勃发展,技术水平不断提升,许多优秀作品在国际市场上崭露头角。从画面渲染到物理引擎,从AI技术到服务器架构,国产游戏已实现质的飞跃。然而,面对全球游戏市场的激烈竞争,国产游戏技术仍然面临诸多挑战。本文将探讨这些挑战,并展望未来的机遇,深入分析IT技术的创新将如何推动行业发展。 国产游戏技术现状 国产游戏在画面渲染、物理引擎、AI

第四次北漂----挣个独立游戏的素材钱

第四次北漂,在智联招聘上,有个小公司主动和我联系。面试了下,决定入职了,osg/osgearth的。月薪两万一。 大跌眼镜的是,我入职后,第一天的工作内容就是接手他的工作,三天后他就离职了。 我之所以考虑入职,是因为 1,该公司有恒歌科技的freex平台源码,可以学学,对以前不懂的解解惑。 2,挣点素材钱,看看张亮002的视频,他用了6000多,在虚幻商城买的吸血鬼游戏相关的素材,可以玩两年。我

nyoj 1038 纸牌游戏

poj 的一道改编题,说是翻译题更恰当,因为只是小幅度改动。 一道模拟题,代码掌控能力比较好,思维逻辑清晰的话就能AC。 代码如下: #include<stdio.h>#include<string.h>#include<algorithm>using namespace std;struct node{char c[5];int rk;char da[5];int nu

牛客小白月赛100部分题解

比赛地址:牛客小白月赛100_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ A.ACM中的A题 #include<bits/stdc++.h>using namespace std;#define ll long long#define ull = unsigned long longvoid solve() {ll a,b,c;cin>>a>>b>

如果出一个名叫白神话悟空的游戏

最近黑神话由于与原著不符引起了原著派的争议。 所以我在摸鱼的时候想到如果游科或者某个别的公司“痛改前非”不夹带私货完全复刻吴承恩百回版剧情制作一个“重走西游路”的游戏,会有一个什么样的销量?(设定为原著派已经多方渠道认证,此游戏的确没有夹带私货,绝大部分复刻了原著剧情) 游戏玩法我想了几类 超长线性有岔路蜈蚣形状地图,蜈蚣的腿部是探索区域和支线,重走西游路线,开篇就是开始取经前唐玄宗御弟cg

牛客小白月赛100(A,B,C,D,E,F三元环计数)

比赛链接 官方讲解 这场比较简单,ABC都很签到,D是个不太裸需要预处理的 B F S BFS BFS 搜索,E是调和级数暴力枚举,F是三元环计数。三元环考的比较少,没见过可能会偏难。 A ACM中的A题 思路: 就是枚举每个边变成原来的两倍,然后看看两短边之和是否大于第三边即可。 不能只给最短边乘 2 2 2,比如 1 4 8 这组数据,也不能只给第二短边乘 2 2 2,比

《黑暗之魂2:原罪学者》是什么类型的游戏 《黑暗之魂》可以在苹果Mac电脑上玩吗?

在宏大的世界观游戏中,《黑暗之魂2:原罪学者》脱颖而出,以其探索性和挑战性征服了全球玩家的心灵。下面我们来看看《黑暗之魂2:原罪学者》是什么类型的游戏,《黑暗之魂2:原罪学者》可以在苹果电脑玩吗的相关内容。 一、《黑暗之魂2:原罪学者》是什么类型的游戏 《黑暗之魂2:原罪学者》作为《黑暗之魂2》的增强版和重制版,是一款FromSoftware制作、BANDAI NAMCO和FromSoft