[第五題]伯俊/1188:ホームページに戻る



これは本当に簡単な問題ですが、いつも細部を逃しています.
人生は反省の連続である.
#include <iostream>


using namespace std;

char board[5][5];

int checkBoard[5][5];

// start 위치 board[r-1][0]
// end   위치 board[0][c-1]
// 하나씩 탐색하다가 , K가 되었는데도 끝나지않으면 종료

int check(char board[5][5] , int checkBoard[5][5], int i , int j , int R, int C , int K , int current) {
	int cnt =0;
	if (current == K) return 0; // 길을 넘어가면 0

	if (current == K-1 && i == 0 && j == C- 1) return 1; // 길 숫자가 맞고 끝에 도착했으면 1
	
	if (checkBoard[i-1][j] == 0 && i != 0 && board[i - 1][j] == '.') { // 방문하지 않은점이면 위로 한칸 움직이기
		checkBoard[i-1][j] = 1;
		cnt += check(board,checkBoard, i - 1, j, R, C, K, current + 1);
		checkBoard[i-1][j] = 0;
	}
	if (checkBoard[i][j+1] == 0 && j != C-1 && board[i][j+1] == '.') { // 오른쪽으로 한칸 움직이기
		checkBoard[i][j+1] = 1;
		cnt += check(board,  checkBoard , i , j+1, R, C, K, current + 1);
		checkBoard[i][j+1] = 0;
	}
	if (checkBoard[i][j-1] == 0 && j != 0 && board[i][j - 1] == '.') { // 오른쪽으로 한칸 움직이기
		checkBoard[i][j-1] = 1;
		cnt += check(board, checkBoard, i, j -1, R, C, K, current + 1);
		checkBoard[i][j-1] = 0;
	}
	if (checkBoard[i+1][j] == 0 && i != R-1 && board[i+1][j] == '.') { // 오른쪽으로 한칸 움직이기
		checkBoard[i+1][j] = 1;
		cnt += check(board, checkBoard, i + 1, j , R, C, K, current + 1);
		checkBoard[i+1][j] = 0;
	}
	return cnt;
}
int main() {
	int R, C, K;

	cin >> R >> C >> K;

	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			checkBoard[i][j] = 0;
		}
	}

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> board[i][j];
		}
	}
	checkBoard[R - 1][0] = 1;
	cout << check(board,checkBoard,  R-1 , 0 , R , C , K, 0);
	return 0;
}
この問題をするとき、以下のものを見逃しました.
  • で最も短い距離だとは誰も言わず、右、上の2つの方向しか考えていません.
    4つの方向を考慮しなければならない.
  • checkBoard[R - 1][0] = 1; この部分を書くのを忘れた
  • それでもポジティブな面は、
    以前見た方法を覚えています.
    if (checkBoard[i-1][j] == 0 && i != 0 && board[i - 1][j] == '.') { // 방문하지 않은점이면 위로 한칸 움직이기
    		checkBoard[i-1][j] = 1;
    		cnt += check(board,checkBoard, i - 1, j, R, C, K, current + 1);
    		checkBoard[i-1][j] = 0;
    	}
    これは、関数を再帰的に記述するときにcheckboardボードを変更してパラメータとして渡し、そのまま変更する方法です.
    かなり有効な方法だと思います.