Có 7 loại hình khối dưới đây
Cho ma trận nhị phân NxN, đếm số lượng mỗi loại hình khối tạo bởi những số 1 trong ma trận.
Lưu ý một hình có thể được xoay theo 4 hướng và 2 hình bất kì đều cách nhau ít nhất 1 khoảng trống.
Input
Dòng đầu là số lượng test case T (T <= 50).
Bắt đầu mỗi test case là kích thước của ma trận N (N< = 1000), N dòng tiếp theo là ma trận nhị phân.
Output
In mỗi test case trên 2 dòng, dòng đầu tiên là “Case #x“, với x là số thứ tự của test case. Dòng tiếp theo bao gồm 7 số là số lượng số hình khối tương ứng của mỗi loại.
Sample
Input
5
5
1 1 1 0 0
0 1 0 1 0
1 0 0 1 0
1 1 0 1 0
1 0 0 1 0
6
1 1 0 1 1 1
0 1 1 0 1 0
1 0 0 0 0 0
1 1 0 0 0 0
0 1 0 0 1 1
0 0 0 0 1 1
…
Output
Case #1
2 0 0 0 1 0 0
Case #2
1 1 1 1 0 0 0
Case #3
1 1 1 1 1 2 0
Case #4
0 0 0 5 4 0 0
Case #5
2 0 0 1 1 0 3
Code Solution:
//BFS cách của Được
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
int n;
int a[1000][1000];
int visitA[1000][1000];
int b[4][4];
int qx[10];
int qy[10];
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };
int Ans[7];
//1=0-3, 2=4-5, 3=6-7, 4=8, 5=9-10, 6=11-14, 7=15-18
int c[19][4][4] = {
//1
{
{1, 1, 1, 0},
{0, 1, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0}
},
{
{0, 1, 0, 0},
{1, 1, 1, 0},
{0, 0, 0, 0},
{0, 0, 0, 0}
},
{
{1, 0, 0, 0},
{1, 1, 0, 0},
{1, 0, 0, 0},
{0, 0, 0, 0}
},
{
{0, 1, 0, 0},
{1, 1, 0, 0},
{0, 1, 0, 0},
{0, 0, 0, 0}
},
//2
{
{0, 1, 1, 0},
{1, 1, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0}
},
{
{1, 0, 0, 0},
{1, 1, 0, 0},
{0, 1, 0, 0},
{0, 0, 0, 0}
},
//3
{
{1, 1, 0, 0},
{0, 1, 1, 0},
{0, 0, 0, 0},
{0, 0, 0, 0}
},
{
{0, 1, 0, 0},
{1, 1, 0, 0},
{1, 0, 0, 0},
{0, 0, 0, 0}
},
//4
{
{1, 1, 0, 0},
{1, 1, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0}
},
//5
{
{1, 1, 1, 1},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0}
},
{
{1, 0, 0, 0},
{1, 0, 0, 0},
{1, 0, 0, 0},
{1, 0, 0, 0}
},
//6
{
{1, 0, 0, 0},
{1, 0, 0, 0},
{1, 1, 0, 0},
{0, 0, 0, 0}
},
{
{0, 0, 1, 0},
{1, 1, 1, 0},
{0, 0, 0, 0},
{0, 0, 0, 0}
},
{
{1, 1, 0, 0},
{0, 1, 0, 0},
{0, 1, 0, 0},
{0, 0, 0, 0}
},
{
{1, 1, 1, 0},
{1, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0}
},
//7
{
{0, 1, 0, 0},
{0, 1, 0, 0},
{1, 1, 0, 0},
{0, 0, 0, 0}
},
{
{1, 1, 1, 0},
{0, 0, 1, 0},
{0, 0, 0, 0},
{0, 0, 0, 0}
},
{
{1, 1, 0, 0},
{1, 0, 0, 0},
{1, 0, 0, 0},
{0, 0, 0, 0}
},
{
{1, 0, 0, 0},
{1, 1, 1, 0},
{0, 0, 0, 0},
{0, 0, 0, 0}
},
};
void re() {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
b[i][j] = 0;
}
}
}
void BFS(int x, int y) {
int st, en;
st = en = 0;
re();
qx[en] = x;
qy[en++] = y;
visitA[x][y] = 1;
int xStart, yStart, xNext, yNext;
while (st != en) {
xStart = qx[st];
yStart = qy[st++];
for (int i = 0; i < 4; i++) {
xNext = xStart + dx[i];
yNext = yStart + dy[i];
if (xNext >= 0 && xNext < n && yNext >= 0 && yNext < n && visitA[xNext][yNext] == 0 && a[xNext][yNext] == 1) {
visitA[xNext][yNext] = 1;
qx[en] = xNext;
qy[en++] = yNext;
}
}
}
int xMin = 2000, yMin = 2000;
for (int i = 0; i < 4; i++) {
if (qx[i] < xMin) {
xMin = qx[i];
}
if (qy[i] < yMin) {
yMin = qy[i];
}
}
for (int i = 0; i < 4; i++) {
b[qx[i] – xMin][qy[i] – yMin] = 1;
}
for (int k = 0; k < 19; k++) {
int dem = 0;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (b[i][j] == 1 && c[k][i][j] == b[i][j]) {
dem++;
}
}
}
//1=0-3, 2=4-5, 3=6-7, 4=8, 5=9-10, 6=11-14, 7=15-18
if (dem == 4) {
if (k >= 0 && k <= 3) {
Ans[0]++;
}
else if (k == 4 || k == 5) {
Ans[1]++;
}
else if (k == 6 || k == 7) {
Ans[2]++;
}
else if (k == 8) {
Ans[3]++;
}
else if (k == 9 || k == 10) {
Ans[4]++;
}
else if (k >= 11 && k <= 14) {
Ans[5]++;
}
else if (k >= 15 && k <= 18) {
Ans[6]++;
}
break;
}
}
}
int main() {
int test;
cin >> test;
for (int tc = 1; tc <= test; tc++) {
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> a[i][j];
visitA[i][j] = 0;
}
}
for (int i = 0; i < 7; i++) {
Ans[i] = 0;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (a[i][j] == 1 && visitA[i][j] == 0) {
BFS(i, j);
}
}
}
cout << “Case #” << tc << endl;
for (int i = 0; i < 7; i++) {
cout << Ans[i] << ” “;
}
cout << endl;
}
return 0;
}
alexishuuuocn 