重庆网站制作和推广公司,海外广告推广公司,常见cms网站源码下载,杭州模板网站建设题目链接:D-剪纸游戏_牛客小白月赛86 (nowcoder.com)
题目描述:
输入描述: 输入第一行包含两个空格分隔的整数分别代表 n 和 m。 接下来输入 n行#xff0c;每行包含 m 个字符#xff0c;代表残缺纸张。 保证#xff1a; 1≤n,m≤10001 字符仅有 . 和 * 两种字符#xf…题目链接: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)
代码
#includebits/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 pairint, 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) {queuePII 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;
}
