[C++]伯俊-#4963島の個数

1932 ワード
白駿 BFS ps テキストリンク
問題の説明

入力

しゅつりょく
各テストボックスについて、島の個数を出力します.
解法
これは典型的なBFS／DFS問題である.
他の問題とは異なり,対角線方向まで上下左右ではなく8方向を考慮すべきである.
それ以外に、気を遣うところはありません.
ソースコード
#include <bits/stdc++.h>
using namespace std;

int board[60][60];
bool vis[60][60];

#define X first
#define Y second

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(false);
	cin.tie(0);

	int n, m;

	while (1) {

		cin >> m >> n;

		int cnt = 0;

		if (n == 0 && m == 0)
			return 0;


		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
			{
				cin >> board[i][j];
				vis[i][j] = 0;
			}


		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (vis[i][j] || board[i][j] == 0) continue;
				queue <pair<int, int>> Q;
				cnt++;
				Q.push({ i, j });

				while (!Q.empty())
				{
					pair<int, int> 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 (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
						if (vis[nx][ny] || board[nx][ny] != 1) continue;

						vis[nx][ny] = 1;
						Q.push({ nx, ny });
					}
				}
			}
		}

			cout << cnt << "\n";
	}
}
フィードバック
確かに直感的に説明できるBFS問題は容易に解決できる.公式を暗記するように暗記するのではなく、潮流を理解することが重要です.
Bootstrap
Day 17