题解 | 剪纸游戏

#include <iostream>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;

struct Grid {
	int x;
	int y;
};

bool compare_grid(Grid a, Grid b) {
	if (a.x != b.x) return a.x < b.x;
	return a.y < b.y;
}

int n, m, ans, cnt = 2;
int direction[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
char c[1005][1005];
Grid grids[1005 * 1005];
int vis[1005][1005];

int main() {
	cin >> n >> m;
	cin.ignore();
	for (int i = 0; i < n; i++) {
		cin.getline(c[i], m + 1);
	}
	for(int i = 0; i < n; i++) {
		for(int j = 0;  j < m; j++) {
			if (!vis[i][j] && c[i][j] != '*') {
				cnt = 0;
				queue<Grid> q;				 
				Grid st;
				st.x = i;
				st.y = j;
				q.push(st);
				vis[st.x][st.y] = 1;
				int result = 1;
				while (!q.empty()) {
					Grid g = q.front();
					q.pop();
					grids[cnt++] = g;
					for (int k = 0; k < 4; k++) {
						int x = g.x + direction[k][0];
						int y = g.y + direction[k][1];
						if (x > -1 && x < n && y > -1 && y < m && !vis[x][y] && c[x][y] != '*') {
							vis[x][y] = 1;
							Grid new_grid;
							new_grid.x = x;
							new_grid.y = y;
							q.push(new_grid); 
						} 
					}
				}
			  	//判断是不是矩形o(n)
				int min_x = 1005, min_y = 1005, max_x = -1, max_y = -1;
				for (int k = 0; k < cnt; k++) {
					min_x = min(min_x, grids[k].x);
					min_y = min(min_y, grids[k].y);
					max_x = max(max_x, grids[k].x);
					max_y = max(max_y, grids[k].y);	
				}
				if ((max_x - min_x + 1) * (max_y - min_y + 1) != cnt) result = 0;
				ans += result; 
			}
  		} 
	}
	cout << ans << endl;    
}
//深搜第一次回溯得到的是轮廓，但是如果中间是空的会误判