#include #include #include #include #include #define MAX 100 using namespace std; int N, M; int start_x, start_y, start_d; int end_x, end_y, end_d; int max_turn = INT_MAX; // 0,1 int map[MAX][MAX]; int visit[MAX][MAX][5]; bool visited[MAX][MAX][5]; typedef struct { int r, c, d; }RCD; queue Q; int dr[5] = { 0, 0,0,1,-1 }; int dc[5] = { 0, 1,-1,0,0 }; // d = 현재방향, i = 가려는 방향 int check_dir(int d, int i) { // 방향 같은 경우 if (d == i) { return 0; } // 반대방향, 명령 2번 필요 else if ((d + i) == 7 || (d + i) == 3) { return 2; } // 명령 1번필요 else return 1; } void push_Q(int nr, int nc, int d, int new_order) { visit[nr][nc][d] = new_order; visited[nr][nc][d] = true; Q.push({ nr,nc,d }); } void check_end(int nr, int nc, int d, int new_order) { if (nr == end_x && nc == end_y) { int turn = check_dir(d, end_d); if (max_turn > turn + new_order) { max_turn = turn + new_order; //push_Q(nr, nc, d, new_order); } } else { push_Q(nr, nc, d, new_order); } } void check_go(int nr, int nc, int i, int r, int c, int d, int turn) { for (int k = 0; k < 2; k++) { nr += dr[i]; nc += dc[i]; if (nr < 1 || nc < 1 || nr > M || nc > N || visited[nr][nc][i] || map[nr][nc] == 1) return; check_end(nr, nc, i, visit[r][c][d] + turn + 1); } } void BFS() { while (!Q.empty()) { RCD out = Q.front(); Q.pop(); int r = out.r, c = out.c, d = out.d; for (int i = 1; i <= 4; i++) { int nr = r + dr[i]; int nc = c + dc[i]; if (nr < 1 || nc < 1 || nr > M || nc > N || visited[nr][nc][i] || map[nr][nc] == 1) continue; int turn = check_dir(d, i); check_end(nr, nc, i, visit[r][c][d] + turn + 1); check_go(nr, nc, i, r, c, d, turn); /*for (int k = 0; k < 2; k++) { nr += dr[i]; nc += dc[i]; if (nr < 1 || nc < 1 || nr > M || nc > N || visited[nr][nc][i] || map[nr][nc] == 1) continue; check_end(nr, nc, i, visit[r][c][d] + turn + 1); }*/ } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(NULL); cin >> M >> N; for (int i = 1; i <= M; i++) { for (int j = 1; j <= N; j++) { cin >> map[i][j]; } } cin >> start_x >> start_y >> start_d; cin >> end_x >> end_y >> end_d; visited[start_x][start_y][start_d] = true; Q.push({ start_x,start_y,start_d }); if (start_x == end_x && start_y == end_y) { int turn = check_dir(start_d, end_d); cout << turn; return 0; } BFS(); cout << max_turn; return 0; }

제출 #129464

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: