[第六題]伯俊/1245:農場管理

この問題もずいぶん間違っている.
しかし、挫折しないでください.人生は長いです.
(コードの時間は短いですが、場外としましょう)

// N X M 농장 -> 2차원배열
// 산봉우리는 몇개가있는가?
~~텍스트~~

// 산봉우리의 정의 - 같은높이를 가지는 (최대높이점 구하는게 아님)
/*8 7
9 3 2 2 1 0 9
3 3 3 2 1 0 9
2 2 2 2 1 0 0
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 9 9 1 1 0
0 1 1 1 9 1 0*/

/*8 7
4 1 2 2 1 0 1
1 1 1 2 1 0 1
2 2 2 2 1 0 0
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0*/

//3개
// 재귀적으로 해결 
// 최대 100 * 70

#include <iostream>

// 0 9
// 9 10
// 10 10
// 2 54
// 3?

using namespace std;

int numMountain = 0;
int gameBoard[101][71];
int check[101][71];
int N, M;
int add = 0;
int dir[8][2] = { {1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1} };

void changeBoard(int gameBoard[101][71], int check[101][71], int i, int j) {
	check[i][j] = 1;
	for (int z = 0; z < 8; z++) {
		if (check[i + dir[z][0]][j + dir[z][1]] != 1 && i + dir[z][0] >= 0 && i + dir[z][0] <= N - 1 && j + dir[z][1] >= 0 && j + dir[z][1] <= M - 1) {
			if (gameBoard[i + dir[z][0]][j + dir[z][1]] == gameBoard[i][j]) {
				check[i + dir[z][0]][j + dir[z][1]] = 1;
				changeBoard(gameBoard, check, i + dir[z][0], j + dir[z][1]);
			}
		}
		if (i+dir[z][0] >= 0 && i + dir[z][0] <= N - 1 && j + dir[z][1] >= 0 && j + dir[z][1] <= M - 1 && gameBoard[i + dir[z][0]][j + dir[z][1]] > gameBoard[i][j]) {
			add = 1;
		}
	}
}

void checkBoard(int gameBoard[100][71], int check[100][71], int i, int j) {
	int temp = gameBoard[i][j];
	add = 0;
	// gameBoard[i][j] = 현재값
	for (int q = 0; q < 8; q++) {
		if (i + dir[q][0] >= 0 && i + dir[q][0] <= N - 1 && j + dir[q][1] >= 0 && j + dir[q][1] <= M - 1) {
			if (gameBoard[i + dir[q][0]][j + dir[q][1]] > gameBoard[i][j]) {
				changeBoard(gameBoard,check,i,j);
				return; // 인접격자가 본인보다 크다면 , 봉우리일수가 없으므로 인접한 모든 격자를 change
			}
			// return이 안되었다면, 본인이 가장 같거나 크다는 뜻
		}
	}
	changeBoard(gameBoard, check, i, j);
	
	if (temp != 0 && add == 0) {
		numMountain += 1;
	}
	
}

int main() {

	numMountain = 0;
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> gameBoard[i][j];
			check[i][j] = 0;
		}
	}


	// 모든 배열에 대해 함수를 시도
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (check[i][j] != 1) { // 봉우리체크가 끝나지 않는 지역의 경우
				checkBoard(gameBoard, check, i, j);
			}
		}
	}
	cout << numMountain;
	return 0;
}

まず習慣を身につけなければならない.
目的もなく始まる前に、私が理解していることを注釈でできるだけ書きます.
この問題は,反例を決定するのは難しすぎて,アルゴリズムの論理実装が間違っているからである.
3 3
1 0 1
1 1 6
2 2 2
このcaseには2つのピークがあり,上部のcheckBoard関数では

if (i+dir[z][0] >= 0 && i + dir[z][0] <= N - 1 && j + dir[z][1] >= 0 && j + dir[z][1] <= M - 1 && gameBoard[i + dir[z][0]][j + dir[z][1]] > gameBoard[i][j])

第6課の第2課は、奉宥利の上の条件文ではないと判断すべきであり、最初はチェック(訪問)が行われたかどうかも確認していた.
これはあまりにも話にならない.
アクセスは存在し、同じ数字が連続している場合、重複アクセスではなくピークとみなされます.
周囲にもっと大きな山があるかどうかを判断するときは、その山を訪れたことがあるかどうかを判断する必要はありません.
個人的には見つけにくい論理的な誤りだが、意味がないわけではない.
テスト用例を勝手に作成する能力を育成した.
これはアルゴリズム解題を行う場合だけでなく,現在個人が行っている組み込み符号化無人機プロジェクトで符号化を行う場合にも利用できる能力であると考えられる.
実際には、符号化テストやウェブページ/埋め込み符号化でも、エラーを探すのは正常ではありません.転送する前にエラーを見つけることが最も重要です.