#1474 : 拆字游戏

描述

小Kui喜欢把别人的名字拆开来，比如“螺”就可以拆成“虫田糸”，小Kui的语文学的不是很好，于是她决定使用编程的方式来解决这个问题。

给出一个01矩阵，1占据的部分即为需要拆的字，如果两个1分享一条边，那么它们连通。连通具有传递性，即如果a、b连通，b、c连通，则a、c连通。

连通的一系列1被看做可以拆出的一块，现在小Kui需要输出这些拆出的块（用一个01矩阵表示，并且要求矩阵的大小尽可能的小）。

为了确保输出的顺序尽可能的和书写的顺序一致，小Kui从每个块中选出最左上角的点（最左侧的点中，最靠上的）作为代表点，然后按照代表点从左到右（若相同则按从上到下）的顺序输出所有拆出的块。

输入

输入的第一行为两个正整数N、M，表示01矩阵的大小。

接下来N行，每行M个01字符，描述一个需要拆的字。

对于40%的数据，满足1<=N,M<=10。

对于100%的数据，满足1<=N,M<=500。

输出

按照代表点从左到右（若相同则按从上到下）的顺序输出所有拆出的块。

对于每个块，先输出其大小，然后用对应的01矩阵表示这个块。

额外的样例

14 2200000000000011111111000000000000001101101100000011000000111111110000001100000011011011000111111110001111111100011011011000000000000001101101100000110000000111111110001111111000000011000000000110000000001101100011111111000111111111000111111000000000001000110110110000000000000000011000000000000000000011100000样例输出
10 90001100000001100001111111101101101101101101101111111100001100000001101101111111110000000105 811111111110110111111111111011011111111118 800110000111111100001100011111111011111101101101100011000
00111000
#include <queue>#include <vector>#include <iostream>using namespace std;const int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};int n, m, mx, my, Mx, My;void floodfill(vector<vector<int>> &a, int x, int y){	a[x][y] = 0;	queue<pair<int, int>> q;	q.push(make_pair(x, y));	while (!q.empty())	{		auto p = q.front();		q.pop();				mx = min(p.first, mx);		my = min(p.second, my);		Mx = max(p.first, Mx);		My = max(p.second, My);				for (int i = 0; i < 4; i++)		{			int xx = p.first + dir[i][0];			int yy = p.second + dir[i][1];			if (xx >= 0 && xx < n && yy >= 0 & yy < m && a[xx][yy] == 1)			{				a[xx][yy] = 0;				q.push(make_pair(xx, yy));			}		}	}}int main(){	freopen( "/home/liyuanshuo/ClionPRoject/hihocoder8/in.in", "r", stdin);	cin >> n >> m;	vector<vector<int>> a(n, vector<int>(m));	for (int i = 0; i < n; i++)		for (int j = 0; j < m; j++)		{			char ch;			cin >> ch;			a[i][j] = ch - '0';		}		auto b = a;	for (int i = 0; i < m; i++)		for (int j = 0; j < n; j++)			if (a[j][i])			{				mx = n; my = m; Mx = -1, My = -1;				floodfill(a, j, i);				cout << Mx - mx + 1 << ' ' << My - my + 1 << endl;				for (int k = mx; k <= Mx; k++)				{					for (int l = my; l <= My; l++)						if (b[k][l] == 1 && a[k][l] == 0)						{							b[k][l] = 0;							cout << 1;						}						else							cout << 0;					cout << endl;				}			}		return 0;}