[伯俊]2012オーガニック白菜py

質問リンク:https://acmicpc.net/problem/1012

💡 アイデア

どのような方法で問題を解決したいかを書いてください.初期メソッドと最終メソッドに差がない場合、少なくとも1つのメソッドを使用することができる.

初期アクセス

は本来どうすればいいのでしょうか、と思っていましたが、しばらくしてそれも正しいと思いましたが、DFSがうまくいかなかっただけです.アクセス履歴の新しい配列は作成されません!私はただ訪問した場所に新しい価格を追加したいだけです.並びの最大サイズが2500なので、3000(ちょっと頭を使ったと思います)で、ジロンもエフレンガも行ける領域を同じ数で構成!やりたかったのに.結局、そこで最大の数字-300-1は、数を数えたくて、、、そして悲惨に誤りを迎えて、、、実施に失敗したため、無限に循環されました.

実際、私はこの方法で2回やったが、だめだったので、解決策を検索した.しかしコードは見ると少し乱れていて、よく読んでいないと、ほほほ

最終アクセス

この時、、、、孟真に絶望のメッセージを与えた~孟真はヒントを与え、それで解いた.だから出る方法は!

私はただ胃を入れたいだけで、ほほほ孟真の言うことを聞いて書いて書いて書いて書いて書いて書いて、自分でまた頭を動かしましたか?

アクセスを記録して2つのアクセス済み配列を作成

訪問していませんが、白菜があれば
1.cnt値++
2.上下左右に回って(衝突をチェックしなければならない)、訪問したことのない白菜があるかどうか見てみましょう
3.ある場合は白菜の位置を記録する
4.白菜がない→終了
5.白菜があって、もう訪問した→終了
これらの内容.

📋 使用仕様

どんなアルゴリズムやテクニックで問題を解決したか教えてください.

DFS

👨🏻‍💻 👩‍💻 コード#コード#

#include <iostream>
using namespace std;

int** visited;
int** arr;
int M, N;

// visited랑 arr배열 재사용 위해 초기화해주는 함수
void init(int row, int col) {
	visited = new int* [row];
	arr = new int* [row];

	for (int i = 0; i < row; i++) {
		visited[i] = new int[col];
		arr[i] = new int[col];
	}

	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			visited[i][j] = 0;
			arr[i][j] = 0;
		}
	}
}

void dfs(int r, int c) {
	if (arr[r][c] == 0)	// 배추 없잖아!
		return;
	if (arr[r][c] == 1 && visited[r][c] == 1)	// 배추 있는데 이미 방문한 곳
		return;
	if (arr[r][c] == 1 && visited[r][c] == 0) {	// 배추 있는데 아직 방문을 안 했네!
		visited[r][c] = 1;	// 방문기록 남기고 갑니다요,,,~

		// 여기서 나오는 조건문은 다 충돌검사 위한 거
		// 그리고 상하좌우 재귀로 탐색하기
		if (r - 1 >= 0)
			dfs(r - 1, c);
		if (r + 1 < N)
			dfs(r + 1, c);
		if (c - 1 >= 0)
			dfs(r, c - 1);
		if (c + 1 < M)
			dfs(r, c + 1);
	}

	return;
}

int main() {

	int T;
	cin >> T;

	while (T--) {
		int K;

		// ㅋㅋ 아니 보통 행-열 이렇게 주는데 얘넨 반대로 주더라
		cin >> M >> N >> K;

		// 난 열-행보단 행-열맨이라 ㅎㅅㅎ
		init(N, M);
		int cnt = 0;

		for (int i = 0; i < K; i++) {
			int x, y;
			cin >> x >> y;
			arr[y][x] = 1;	// 배추 있는 곳 위치 표시
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				// 배추 있는데 방문 안 한 곳만
				if (arr[i][j] == 1 && visited[i][j] == 0) {
					cnt++;	 // 개수 더해주고
					dfs(i, j);	// 거기서부터 탐색할랭
				}
				else;
			}
		}

		cout << cnt << "\n";

	}

	return 0;
}

足りないところ

ソリューションに近づく前に残念な部分を書いてください.ソリューションを参考にして、修正箇所を書いてください.ソリューションへのリンクを書いてください.実装がスムーズであれば、省略できます.

私はこれが私の考えが複雑すぎるためなのか、それとも、ただよく実現できなかっただけなのか分かりませんが、このきっかけで、もう一度!これはDFSを実行する機会です.ドン・ファン

学識

この問題で学んだことを書いてください.あるアルゴリズム,符号化方法,資料構造などを理解した.文法要素もいいです.あまり多くなければ省略できます.

これくらいならDFSに出てもいいのでは?

次の問題も全く同じ問題です.これを解いて次の1つで解くと完全に収穫があって本当に福を貼ることができます

2468号：安全区域