글 읽기 - 반례가 있을까요?

colorxxx 5년 전 0

게시판에 있는 테케 다 맞는데 틀렸다고 나오네요...

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int N, M, ans;
int map[11][11];

int dr[5] = { -1,0,1,0,0 };
int dc[5] = { 0,1,0,-1,0 };
struct state {
	int r; int c; int brok; int time; int bridge;
};
void show() {

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			//cout << map[i][j]<<" ";
			printf("%d", map[i][j]);
		}
		cout << endl;
	}
	cout << endl;

}
int main() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> map[i][j];
		}
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (map[i][j] == 0) {

				if (map[i + dr[0]][j + dc[0]] == 1 && map[i + dr[2]][j + dc[2]] == 1) {//위아래
					map[i][j] = 0;
				}
				else if (map[i + dr[1]][j + dc[1]] == 1 && map[i + dr[3]][j + dc[3]] == 1) {//오른쪽왼쪽
					map[i][j] = 0;
				}
				else if (i + dr[0] == 0 && map[i + dr[2]][j + dc[2]] == 1 || map[i + dr[0]][j + dc[0]] == 1 && i + dr[2] == N + 1) {
					map[i][j] = 0;
				}
				else if (j + dc[1] == N + 1 && map[i + dr[3]][j + dc[3]] == 1 || map[i + dr[1]][j + dc[1]] == 1 && j + dc[3] == 0) {

				}
				else map[i][j] = -1;
			}
		}
	}//이동할수없는 절벽 체크

	 //show();
	queue<state> q;
	q.push({ 1,1,1,0,1 }); //r,c,brok,time,bridge
	
	while (!q.empty()) {
		int r = q.front().r; int c = q.front().c; int brok = q.front().brok; int time = q.front().time;
		int bridge = q.front().bridge;


		q.pop();
		if (r == N && c == N) {
			ans = time;
			//if (brok == 1) ans -= 1;
			break;
		}

		for (int i = 0; i < 4; i++) {//멈추는것까지 체크!
			if (i == 0 || i == 3) continue;//위쪾, 왼쪽으로가는경우(방문한경로재방문) 제외

			int nr = r + dr[i]; int nc = c + dc[i];
			if (1 <= nr&&nr <= N && 1 <= nc&&nc <= N) {

				if (map[nr][nc] == 0) {//만약에 다리를 놓을 수 있는 오작교라면
					if (brok == 1 && bridge == 1) {
						if ((time + 1) % M == 0)
							q.push({ nr,nc,0,time + 1,0 });//다리를 놓는다
						else if ((time + 1) % M != 0)
							q.push({ r,c,brok,time + 1,bridge });
					}
				}

				else if (map[nr][nc] >= 2) {//주기마다 생기는 오작교
					if ((time + 1) % map[nr][nc] == 0 && brok == 1) {//건너갈 수 있는 시간이라면&&오작교를 연속으로 지나지 않는경우
						q.push({ nr,nc,0,time + 1,bridge });
					}
					else if ((time + 1) % map[nr][nc] != 0 && brok == 1) {//만약 오작교를 지나오지않은 상태에서 오작교시간때까지 기다린다.
						q.push({ r,c,1,time + 1,bridge });
					}
				}


				else if (map[nr][nc] == 1) {//그냥 이동할수있는 길
					q.push({ nr,nc,1,time + 1,bridge });
				}
			}
		}

	}


	cout << ans;
	//벽부시며 이동하기, 오작교 연속이동불가 , 오작교는 하나이상 가능

}

//위로가는 경우도 체크해야되는것같은데..
//70번줄 brok==1 바꿔보기. 틀릴걸?,시간조건도 바꿔보기
//15~16xor로 해보기!
//depth->다음 depth 이해가 잘 안되네..

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례가 있을까요?

colorxxx 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말