#include #include #include #define MAX 102 using namespace std; int map[MAX][MAX] = {0}; int cost_map[MAX][MAX] = { 0 }; //2차원 배열 0999로 초기화 int visited[MAX][MAX] = {0}; int row, col, start_x, start_y, start_dir, end_x, end_y, end_dir; int nx, ny, ndir, dsum; int dx[4] = { 1,-1,0,0 }; int dy[4] = { 0,0,1,-1 }; int direction[4] = { 1,2,3,4 }; //동 1 서 2 남 3 북 4 int answer = 0x7FFFFFFF; //padding영역을 1로 채워주며 입력받는다. void input() { cin >> row >> col; for (int i = 0; i < row + 2; i++) { for (int j = 0; j < col + 2; j++) { if (i == 0 || i == row + 1 || j == 0 || j == col + 1) { map[i][j] = 1; } else { cin >> map[i][j]; } } } cin >> start_y >> start_x >> start_dir; cin >> end_y >> end_x >> end_dir; //cost_map 초기화 for (int i = 0; i < row + 2; i++) { for (int j = 0; j < col + 2; j++) { cost_map[i][j] = 0x7FFFFFFF; } } } //아마 cost_map을 만들어 나가야 할듯? void dfs(int x, int y, int dir, int command_cnt) { if (command_cnt > answer) return;//가지치기, count가 answer을 넘어가면 더이상 진행하지 않고 종료 if (x == end_x) { if (y == end_y) { //종료조건 if (dir != end_dir) { dsum = dir + end_dir; if (dsum == 3 || dsum == 7) {//2번인 경우 command_cnt += 2; } else { command_cnt += 1; } } answer = min(answer, command_cnt); return; } } cost_map[y][x] = command_cnt; int tmp; for (int i = 0; i < 4; i++) { nx = x + dx[i]; ny = y + dy[i]; ndir = direction[i]; if (map[ny][nx] == 0) { if (dir != ndir) {//방향전환이 이뤄진 경우 1번인지 2번인지 check dsum = dir + ndir; if (dsum == 3 || dsum == 7) {//2번인 경우 tmp = 3; } else { tmp = 2; } } else { if (x == start_x) { if (y == start_y) { tmp = 1; } } else tmp = 0; } //cost_map에 기록 if (cost_map[ny][nx] >= command_cnt + tmp) { dfs(nx, ny, ndir, command_cnt + tmp); //여기서 명령어를 체크해서 들어가야 한다. 이게 이 문제의 핵심 } } } return; } int main() { input(); dfs(start_x, start_y, start_dir, 0); cout << answer << endl; return 0; }

제출 #126190

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: