题解 | #剪纸游戏#

链接https://ac.nowcoder.com/acm/contest/73450/D

题目如上。

此题考查一个图的深度或者广度优先遍历。

此题的难点在于判断是否是一个长方形，我是在广度优先的时候记录了所走过的方块数量cnt,和所有点的最大最小横纵坐标，即maxi,maxj,mini,minj,按照矩形的面积(maxi-mini+1)*(maxj-minj+1),如果cnt等于面积，就代表构成一个矩形。题目较为简单，与LeetCode中一道叫做岛屿数量 的题类似，不一样的就是这道题限定了要求是矩形。 用C++实现的代码如下：

#include<iostream>
#include<vector>
#include<fstream>
#include<queue>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
struct dot {
	int i;
	int j;
	dot(int i, int j) {
		this->i = i;
		this->j = j;
	}
};
bool answer(vector<vector<char>>& Mat,int i, int j,int col,int row) {
	int maxi = i,mini = i, minj = j, maxj = j;
	int cnt = 1;//计算小方格的个数;
	queue<dot>qu;
	int dx[] = { 0,1,0,-1 };
	int dy[] = { 1,0,-1,0 };
	qu.push(dot(i, j));
	Mat[i][j] = '*';
	while (!qu.empty()) {
		dot temp = qu.front(); qu.pop();
		for (int k = 0; k < 4; k++) {
			int tempX = temp.i + dx[k];
			int tempY = temp.j + dy[k];
			if (tempX >= 0 && tempX < col && tempY >= 0 && tempY < row && Mat[tempX][tempY] == '.') {
				Mat[tempX][tempY] = '*';
				cnt++;
				qu.push(dot(tempX, tempY));
				if (tempX < mini)mini = tempX;
				if (tempX > maxi)maxi = tempX;
				if (tempY < minj)minj = tempY;
				if (tempY > maxj)maxj = tempY;
			}
		}
	}
	int width = maxi - mini + 1;
	int length = maxj - minj + 1;
	return cnt == width * length;
}
int main() {
	int col, row;
	cin >> col >> row;
	char c;
	vector<vector<char>>Mat(col);
	for (int i = 0; i < col; i++) {
		for (int j = 0; j < row; j++) {
			cin >> c;
			Mat[i].push_back(c);
		}
	}
	int cnt = 0;
	for (int i = 0; i < col; i++) {
		for (int j =0; j < row; j++) {
			if (Mat[i][j] == '.') {
				bool a = answer(Mat, i, j, col, row);
				if (a) { cnt++; }
			}
		}
	}
	cout << cnt;
}