[第五題]伯俊/1188:ホームページに戻る
21075 ワード
これは本当に簡単な問題ですが、いつも細部を逃しています.
人生は反省の連続である.
#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;
}
この問題をするとき、以下のものを見逃しました.4つの方向を考慮しなければならない.
以前見た方法を覚えています.
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ボードを変更してパラメータとして渡し、そのまま変更する方法です.かなり有効な方法だと思います.
Reference
この問題について([第五題]伯俊/1188:ホームページに戻る), 我々は、より多くの情報をここで見つけました https://velog.io/@plackyou123/다섯번째-문제-백준-1189-컴백홈テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol