-
-
Save pdu/6e950a13964701507252 to your computer and use it in GitHub Desktop.
Given a 2–d matrix , which has only 1’s and 0’s in it. Find the total number of connected sets in that matrix. Explanation:
Connected set can be defined as group of cell(s) which has 1 mentioned on it and have at least one other cell in that set with which they share the neighbor relationship. A cell with 1 in it and no surrounding neighbor havi…
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <stdio.h> | |
| #include <string.h> | |
| #define MAXN 1010 | |
| struct node | |
| { | |
| int x, y; | |
| node(): x(0), y(0) | |
| {} | |
| node(int xx, int yy): x(xx), y(yy) | |
| {} | |
| }; | |
| int n; | |
| int f[MAXN][MAXN]; | |
| node g[MAXN][MAXN]; | |
| const int d[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}}; | |
| node get_root(int i, int j) | |
| { | |
| if (g[i][j].x == i && g[i][j].y == j) | |
| return g[i][j]; | |
| else | |
| return g[i][j] = get_root(g[i][j].x, g[i][j].y); | |
| } | |
| bool in_bound(int i, int j) | |
| { | |
| return i >= 0 && i < n && j >= 0 && j < n; | |
| } | |
| void solve() | |
| { | |
| for (int i = 0; i < n; ++i) | |
| for (int j = 0; j < n; ++j) | |
| if (f[i][j] == 1) | |
| { | |
| g[i][j].x = i; | |
| g[i][j].y = j; | |
| } | |
| for (int i = 0; i < n; ++i) | |
| for (int j = 0; j < n; ++j) | |
| if (f[i][j] == 1) | |
| { | |
| node fij = get_root(i, j); | |
| for (int k = 0; k < 8; ++k) | |
| { | |
| int ni = i + d[k][0], nj = j + d[k][1]; | |
| if (in_bound(ni, nj) && f[ni][nj] == 1) | |
| { | |
| node fninj = get_root(ni, nj); | |
| g[fninj.x][fninj.y] = fij; | |
| } | |
| } | |
| } | |
| int ret = 0; | |
| for (int i = 0; i < n; ++i) | |
| for (int j = 0; j < n; ++j) | |
| if (f[i][j] == 1) | |
| { | |
| node fij = get_root(i, j); | |
| if (i == fij.x && j == fij.y) | |
| ret++; | |
| } | |
| printf("%d\n", ret); | |
| } | |
| int main() | |
| { | |
| int T; | |
| scanf("%d", &T); | |
| while (T--) | |
| { | |
| scanf("%d", &n); | |
| for (int i = 0; i < n; ++i) | |
| for (int j = 0; j < n; ++j) | |
| scanf("%d", &f[i][j]); | |
| solve(); | |
| } | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Why you call solve() before all the data are read?