アルゴリズム::白準::DFS::2667:番号のみ

12017 ワード
白駿 DFS アルゴリズム#アルゴリズム# テキストリンク

質問する



質問へのアクセス


問題を理解する

  • この問題は、典型的な単純なDFSまたはBFS問題タイプである.
    より正確にはDFSに詳しいタイプです.
    (DFSは再帰(スタック)を使用するため、コード行数は4~6行しかかかりません.)
  • 2main()のような外部関数でfor()文を迂回して、DFSまたはVFSが2次元配列内のすべての未アクセスポイントを処理するのを支援します.
  • より多くの接続点がなくて続行できない場合、ユニットをカウントします.
  • は、2 D配列をナビゲートし、アクセスされていない他のポイントにポイントを見つけます.
    • 未アクセスのポイントがなくなるまで、この手順を繰り返します.

    コード#コード#

    #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, cnt, d[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
bool map[27][27], visited[27][27];

void dfs(int y, int x) {
	cnt++;
	visited[y][x] = true;
	for (int i = 0; i < 4; ++i) {
		int ny = y + d[i][0], nx = x + d[i][1];
		if (!visited[ny][nx] && map[ny][nx]) dfs(ny, nx);
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N;
	string row;
	for (int y = 1; y <= N; ++y) {
		cin >> row;
		for (int x = 1; x <= N; ++x)
			map[y][x] = (row[x - 1] == '1') ? true : false;
	}
	vector<int> ans;
	for (int y = 1; y <= N; ++y)
		for (int x = 1; x <= N; ++x)
			if (map[y][x] && !visited[y][x])
				dfs(y, x), ans.push_back(cnt), cnt = 0;
	sort(begin(ans), end(ans));
	cout << ans.size() << '\n';
	for (int i : ans) cout << i << '\n';
}

    結果


    spin_lock、spin_lock_bh、spin_lock_irq、spin_lock_IRqsaveの使用
    HTTP状態コード