# 11994: 【原1994】二哥的地图

### 题目描述

author: qujun 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1994

## 样例输入

3 3
0 -1 0
-1 0 -1
0 -1 0


## 样例输出

5


## FineArtz's solution

/* 二哥的地图 */
#include <iostream>
#include <cstring>
using namespace std;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int a[505][505];
int n, m;

bool check(int x, int y){
if (x < 1 || x > n || y < 1 || y > m || a[x][y] != 0) return false;
return true;
}

void floodfill(int x, int y, int cnt){
a[x][y] = cnt;
for (int i = 0; i != 4; ++i){
int nextx = x + dx[i];
int nexty = y + dy[i];
if (check(nextx, nexty)){
floodfill(nextx, nexty, cnt);
}
}
}

int main(){
memset(a, 0, sizeof(a));
cin >> n >> m;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
cin >> a[i][j];
int cnt = 0;
for (int i = 1; i <= n; ++i){
for (int j = 1; j <= m; ++j){
if (a[i][j] == 0){
++cnt;
floodfill(i, j, cnt);
}
}
}
cout << cnt << endl;
return 0;
}


## ligongzzz's solution

#include "iostream"
#include "cstdio"
using namespace std;

bool map[509][509] = { 0 };
int dx[] = { 0,1,0,-1 },
dy[] = { 1,0,-1,0 };
int n, m;
void dfs(int x, int y) {
map[x][y] = false;
for (int i = 0; i < 4; ++i) {
if (x + dx[i] >= 0 && x + dx[i] < n && y + dy[i] >= 0 && y + dy[i] < m && map[x + dx[i]][y + dy[i]])
dfs(x + dx[i], y + dy[i]);
}
}

int main() {
scanf("%d %d", &n, &m);

for(int i=0;i<n;++i)
for (int j = 0; j < m; ++j) {
int temp;
scanf("%d", &temp);
map[i][j] = (bool)(temp + 1);
}

int cnt = 0;
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
if (map[i][j]) {
++cnt;
dfs(i, j);
}

cout << cnt;

return 0;
}


## Neight99's solution

#include <iostream>

using namespace std;

const int maxN = 5e2 + 10;

int N = 0, M = 0, worldMap[maxN][maxN] = {0}, ans = 0;

void DFS(int x, int y);

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

cin >> N >> M;

for (int i = 0; i < N + 2; i++) {
for (int j = 0; j < M + 2; j++) {
if (i == 0 || i == N + 1 || j == 0 || j == N + 1) {
worldMap[i][j] = 0;
} else {
int temp;
cin >> temp;
worldMap[i][j] = temp + 1;
}
}
}

for (int i = 0; i < N + 2; i++) {
for (int j = 0; j < M + 2; j++) {
if (worldMap[i][j]) {
ans++;
DFS(i, j);
}
}
}

cout << ans;

return 0;
}

void DFS(int x, int y) {
if (!worldMap[x][y]) {
return;
} else {
worldMap[x][y] = 0;
DFS(x - 1, y);
DFS(x + 1, y);
DFS(x, y - 1);
DFS(x, y + 1);
}
}


## skyzh's solution

#include <iostream>
using namespace std;

int MAP[500][500];
int N, M;
bool visited[500][500] = { 0 };

void visit(int x, int y) {
static int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
for (int d = 0; d < 4; d++) {
int _x = x + dir[d][0];
int _y = y + dir[d][1];
if (_x >= 0 && _y >= 0 && _x < N && _y < M) {
if (!visited[_x][_y] && MAP[_x][_y] == 0) {
visited[_x][_y] = true;
visit(_x, _y);
}
}
}
}

int main() {
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> MAP[i][j];
}
}
int c = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (!visited[i][j] && MAP[i][j] == 0) {
visit(i, j);
++c;
}
}
}
cout << c << endl;
return 0;
}


## yyong119's solution

#include <cstdio>
#include <cstring>
#include <queue>
#define MAX_N 505
using namespace std;
struct Node {
int x, y;
Node(int p = 0, int q = 0): x(p), y(q) {}
};
const int ac[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int n, m, cnt;
int map[MAX_N][MAX_N];
queue<Node> q;
char ch = getchar(); int res = 0, flag = 1;
while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '-') flag = -1, ch = getchar();
while (ch >= '0' && ch <= '9')
res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
return res * flag;
}
int main() {
for (register int i = 0; i < n; ++i)
for (register int j = 0; j < m; ++j)
for (register int i = 0; i < n; ++i)
for (register int j = 0; j < m; ++j)
if (!map[i][j]) {
++cnt;
q.push(Node(i, j)); map[i][j] = 1;
while (!q.empty()) {
Node cur = q.front(); q.pop();
for (register int k = 0; k < 4; ++k) {
int x = cur.x + ac[k][0], y = cur.y + ac[k][1];
if (x >= 0 && x < n && y >= 0 && y < m && !map[x][y]) {
map[x][y] = 1;
q.push(Node(x, y));
}
}
}
}
printf("%d", cnt);
return 0;
}


## Zsi-r's solution

#include <iostream>

using namespace std;

class DisjointSet{
private:
int size;
int *parent;
public:
DisjointSet(int s);
~DisjointSet() { delete[] parent; }
void Union(int root1, int root2);
int Find(int x);
void isOne(int x);
int countCountry();
void print();
};

void DisjointSet::print()
{
for (int i = 0; i < size;i++)
cout << parent[i] << ' ';
cout << endl;
}

int DisjointSet::countCountry()
{
int count = 0;
for (int i = 0; i < size;i++)
{
if (parent[i] < 0)
count++;
}
return count;
}

void DisjointSet::isOne(int x)
{
parent[x] = 0;
}

DisjointSet::DisjointSet(int s)
{
size = s;
parent = new int[size];
for (int i = 0; i < size;i++)
parent[i] = -1;
}

int DisjointSet::Find(int x)
{
if (parent[x]<0)
return x;
return parent[x] = Find(parent[x]);
}

void DisjointSet::Union(int root1,int root2)
{
if (root1==root2)
return;
if (parent[root1]>parent[root2])
{
parent[root2] += parent[root1];
parent[root1] = root2;
}
else
{
parent[root1] += parent[root2];
parent[root2] = root1;
}
}

int main()
{
int m, n;
cin >> n >> m;
int **array = new int *[n];
for (int i = 0; i < n;i++)
{
array[i] = new int[m];
for (int j = 0; j < m;j++)
{
cin >> array[i][j];
}
}

//输入的第一行
DisjointSet djs(n * m);
if(array[0][0]==-1)
djs.isOne(0);

for (int i = 1; i < m; i++)
{
if (array[0][i] == -1)
djs.isOne(i);
else
if (array[0][i-1]==0)
djs.Union(djs.Find(i), djs.Find(i - 1));
}

//接下来的n-1行
for (int i = 1; i < n; i++)
{
if (array[i][0]==-1)
djs.isOne(i* m);
else
if (array[i-1][0]==0)
djs.Union(djs.Find((i - 1) * m), djs.Find(i * m));
}

for (int i = 1; i < n; i++)
{
for (int j = 1; j < m; j++)
{
if (array[i][j]==-1)
djs.isOne(i * m + j);
else
{
if (array[i][j-1]==0)
djs.Union(djs.Find(i * m + j - 1), djs.Find(i * m + j));
if (array[i-1][j]==0)
djs.Union(djs.Find(i * m - m + j), djs.Find(i * m + j));
}
}
}

cout << djs.countCountry() << endl;
return 0;
}