和大伙伴做题-gym C. Figures

2024-06-01 21:32

文章标签 gym 做题伙伴 figures

本文主要是介绍和大伙伴做题-gym C. Figures，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

You are given a map divided into n × m square fields which are colored. We call a subset of fields of the same color a Figure, if it is:

in one piece: for every two fields in the Figure, there is a path between them composed of side-adjacent fields belonging to the Figure,
maximal: every field from outside the Figure that is adjacent to it has a different color.

Figures A and B are considered identical (they might be colored differently) if you can move A onto B so that every field of B is covered by a field of A and every field of A covers a field from B, without turning the Figure. Calculate the number of different Figures on the given map.

Input

In the first line of input there is an integer z - the number of test cases. Then, z test cases follow.

First line of a test case contains two integers, n and m (1 ≤ n, m ≤ 1000) - number of rows and columns of the map. In next n lines you are given the description of rows on the map: m integers which are nonnegative and no greater than 10⁹. These integers are the colors of fields in the map.

Output

For each test case, print one line with one integer: the number of different figures.

Sample test(s) 
input 
1
5 5
1 1 2 2 2
3 1 3 3 4
3 4 4 3 4
5 5 5 2 2
1 1 1 6 2
output 
5

题意:给定一个图，求出不同形状的块有几种。

思路:我自己想用二维数组记录下拼图形状在插入到set，可是好像set不太支持哦。。。然后大伙伴说可以利用pair保存点，用set保存点集的方法来保存形状，大伙伴实在机智得我整个人都不行了。f@ck。

代码:

#include <stdio.h>
#include <string.h>
#include <set>
using namespace std;
const int d[4][2] = {{0, 1}, {-1, 0}, {1, 0}, {0, -1}};int t, n, m, g[1005][1005], vis[1005][1005];typedef pair<int ,int> pi;
set<pi> aa;
set<set<pi> > bb;void dfs(int x, int y, int num, int a, int b) {vis[x][y] = 1;aa.insert(make_pair(x - a, y - b));for (int i = 0; i < 4; i++) {int xx = x + d[i][0];int yy = y + d[i][1];if (num == g[xx][yy] && !vis[xx][yy] && xx >= 0 && xx < n && yy >= 0 && yy < m) {dfs(xx, yy, num, a, b);}}
}
int main() {scanf("%d", &t);while (t --) {memset(vis, 0, sizeof(vis));bb.clear();int count = 0;scanf("%d%d", &n, &m);for (int i = 0; i < n; i ++)for (int j = 0; j < m; j ++)scanf("%d", &g[i][j]);for (int i = 0; i < n; i ++)for (int j = 0; j < m; j ++) {if (!vis[i][j]) {aa.clear();dfs(i, j, g[i][j], i, j);if (bb.find(aa) == bb.end()) {bb.insert(aa);count ++;}}}printf("%d\n", count);}return 0;
}

这篇关于和大伙伴做题-gym C. Figures的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！