牛客小白月赛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;
}