TLE 질문
TLE가 뜨네요
불이 나는 경로를 그때마다 만들어줘서 그런건가 싶어서 처음에 불이나는 경로를 전부 만들어주고 시작했는데도 여전히 TLE가 뜹니다
최대 지도 크기가 1000*1000 = 백만이니까, 처음 불나는거 전부 계산할 때 최대 백만번 , 길 찾는거 최대 백만번, 처음 지도 입력받을 때 m_i, m_f 두개 합쳐서 대충 이백만번 치면 사백만번인데 1초안에 끝나지 않나요?
어딜 고쳐야할까요
std::queue를 쓰는게 문제인가 싶어서 직접 queue를 구현했습니다.
qq배열을 백만크기로 잡고 대충 해보니 segment fault가 나오네요
모든 좌표를 다 넣어도 백만이라 qq가 넘치는일이 절대 없을텐데 이상합니다
코드에서 한번 확인한 길은 확인하지 않도록 검사하는데 이 부분이 잘못된건가요?
원형큐를 사용하니까 WA가 뜨네요
원형큐에서 만약 큐가 꽉 찬다면
void* a;
while (1) a = malloc(1000000);
를 통해 MLE가 나오도록(?) 했는데 MLE가 안뜨는걸 보니 이제 큐 문제는 해결된 것 같습니다 (최적화때문에 저 코드가 사라지진 않겠죠?)
제 알고리즘의 어디가 잘못된건가요?
현재 위치에서 4방향으로 이동하는데, 가봤던곳이거나 벽이거나 불이난( + 다음턴에 불이날)곳이면 가보지 않도록 했습니다
또한 맵의 가장자리 (i= 0 or R, j= 0 or C)에 도달하면 탈출에 성공한거라고 판단했습니다
잘못된게 없어보이는데 틀린곳좀 찾아주시면 감사하겠습니다
불씨가 하나만 있다고 한 적은 없습니다.
####
#JF.
#F..
같이 불씨가 2개 이상인 데이터라던가
J...
#....
같이 불씨가 하나도 없는 데이터를 테스트해보세요.
.
아니 이럴수가 F가 1개가 아닐 수 있다니...
감사합니다