#include using namespace std; #define BJ1726 #ifdef BJ1726 #include class node { public: int y = -1, x = -1, time = -1, direction = -1;//1, 2, 3, 4 node(int y, int x, int t, int direc) { this->y = y; this->x = x; time = t; direction = direc; } node() {} //클래스 연산자 오버로딩을 할때는 함수 정의 부분에 cnost를 붙여야 한다. //이 const의 의미는 함수 안에 대입하는 연산이 없다는 의미이다. bool operator < (const node& next) const { return this->time > next.time; } }; int direcy[4] = { 0, 0, 1, -1 }; int direcx[4] = { 1, -1, 0, 0 }; priority_queue pq; int map[100][100]; int checkLen[100][100][4]; int M, N; node start, goal; void printMap() { cout << "--------------------------------------\n"; for (int k = 0; k < 4; k++) { for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { if (checkLen[i][j][k] == 200) cout << '-' << ' '; else cout << checkLen[i][j][k] << ' '; } cout << '\n'; } cout << '\n'; } } int calDirecost(int dire1, int dire2) { int temp; if (dire1 > dire2) { temp = dire2; dire2 = dire1; dire1 = temp; } if (dire1 == dire2) return 0; if (dire1 == 0 && dire2 == 1 || dire1 == 2 && dire2 == 3) return 2; return 1; } void bfs() { node cur; int tempy, tempx, tempLen; pq.push(start); while (!pq.empty()) { cur = pq.top(); pq.pop(); //cout << "pop y : " << cur.y << " x : " << cur.x << '\n'; for (int i = 0; i < 4; i++) { for (int j = 0; j <= 3; j++) { tempy = cur.y + j * direcy[i]; tempx = cur.x + j * direcx[i]; //cout << "check y : " << tempy << " x : " << tempx << " direction : " << i << '\n'; if (tempy >= 0 && tempy < M && tempx >= 0 && tempx < N) { if (map[tempy][tempx] == 0) { tempLen = cur.time + calDirecost(cur.direction, i); if (j != 0) tempLen++; if (tempLen < checkLen[tempy][tempx][i]) { checkLen[tempy][tempx][i] = tempLen; if (tempy == goal.y && tempx == goal.x && i == goal.direction) return; //cout << "push y : " << tempy << " x : " << tempx << " direction : " << i << " time : " << tempLen << '\n'; pq.push(node(tempy, tempx, tempLen, i)); } } else { //cout << "break y : " << tempy << " x : " << tempx << " direction : " << i << '\n'; break; } } } } //printMap(); } } void initCheckLen() { for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { for (int k = 0; k < 4; k++) { checkLen[i][j][k] = 200; } } } } int main() { int sty, stx, std, eny, enx, endi; cin >> M >> N; for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { cin >> map[i][j]; } } cin >> sty >> stx >> std >> eny >> enx >> endi; start = node(sty - 1, stx - 1, 0, std - 1); goal = node(eny - 1, enx - 1, 0, endi - 1); initCheckLen(); checkLen[sty - 1][stx - 1][std - 1] = 0; bfs(); cout << checkLen[eny - 1][enx - 1][endi - 1]; } #endif

제출 #158988

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: