[21414][伯俊/BOJ]4963号島の個数
1865 ワード
質問する
にゅうしゅつりょく
に答える
dfsを使用して問題を解決できます.
一般的なdfs問題は上下左右に近いが,この問題は対角線に近づくことができる.
したがって,dx,dy配列では,上下左右および対角線の4箇所の座標に8個の座標を配置すればよい.
int dx[8] = { -1, 0, 1, 0, 1, 1, -1, -1 };
int dy[8] = { 0, 1, 0, -1, 1, -1, 1, -1 };
コード#コード#
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int board[52][52];
bool vis[52][52];
int dx[8] = { -1, 0, 1, 0, 1, 1, -1, -1 };
int dy[8] = { 0, 1, 0, -1, 1, -1, 1, -1 };
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
while (true)
{
int w, h;
cin >> w >> h;
if (w == 0 && h == 0)
break;
for (int i = 0; i < h; ++i)
for (int j = 0; j < w; ++j)
cin >> board[i][j];
int num = 0;
for (int i = 0; i < h; ++i)
{
for (int j = 0; j < w; ++j)
{
if (vis[i][j] || board[i][j] == 0) continue;
num++;
queue <pair<int, int>> Q;
vis[i][j] = 1;
Q.push({ i,j });
while (!Q.empty())
{
auto cur = Q.front(); Q.pop();
for (int dir = 0; dir < 8; ++dir)
{
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if (vis[nx][ny] || board[nx][ny] == 0) continue;
if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
vis[nx][ny] = 1;
Q.push({ nx,ny });
}
}
}
}
cout << num << '\n';
fill(vis[0], vis[0] + 52 * 52, 0);
}
}
Reference
この問題について([21414][伯俊/BOJ]4963号島の個数), 我々は、より多くの情報をここで見つけました https://velog.io/@kwkim95/210414백준BOJ-4963번-섬의-개수テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol