글 읽기 - 진짜 다 맞는거 같은데 바로틀리네요 반례부탁드립니다ㅠ

jms020820 1년 전 0

제자리 기다리는 경우는 밤일 때 벽수기를 기다리는 경우만 있다고 생각해서 밤 일때 벽부수면 경로를 +2하고 밤낮을 바꾸지 않는 식으로하고

나머지는 밤낮바꾸면서 BFS돌렸습니다. 방문여부는 방문하지 않았으면 방문하고 방문한곳이면 더 적은 경로일때만 방문했습니다

게시판 반례랑 생각해본 반례는 다 해봤는데 반례를 못찾았네요 ㅠㅠ

고수님들 부탁해요 ㅠㅜ

_____________

밤낮 구별해서 방문여부 기록했더니 통과됐네요.... 아래코드 문제점은 BFS에서 경로를 +2해서 생긴거같은데

문제가 생기는 이유가 무었인가요???

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
int visit[1011][1011][12];
char map[1011][1011];
int dx[4] = {0,1,0,-1};
int dy[4] = {-1,0,1,0};
typedef struct XY{
	int x,y,bk_num;
	bool day;
}XY;
XY st = {0,0,0,true},end;
int bk;
typedef struct NODE{
	struct NODE *next,*prev;
	XY data;
}NODE;
void push(NODE *head,XY data);
XY pop(NODE *tail);
void BFS(NODE *head,NODE* tail);
int main(){
	NODE *head = malloc(sizeof(NODE));
	NODE *tail = malloc(sizeof(NODE));
	head->next = tail;
	head->prev = NULL;
	tail->next = NULL;
	tail->prev = head;
	int n,m,b,q;
	scanf("%d %d %d",&n,&m,&b);
	for(q=0;q<n;q++){
		scanf(" %s",map[q]);
	}
	end.x = n,end.y = m;
	bk = b;
	BFS(head,tail);
	int min = 999999;
	for(q=0;q<=b;q++){
		if(visit[end.x-1][end.y-1][q]!=0&&min>visit[end.x-1][end.y-1][q])
			min = visit[end.x-1][end.y-1][q];
	}
	if(min==999999)
		printf("%d",-1);
	else
		printf("%d",min);
	return 0;
}
void push(NODE *head,XY data){
	NODE *new = malloc(sizeof(NODE));
	new->next = head->next;
	head->next->prev = new;
	new->prev = head;
	head->next = new;
	new->data = data;
}
XY pop(NODE *tail){
	NODE *del = tail->prev;
	tail->prev = del->prev;
	del->prev->next = tail;
	XY k = del->data;
	free(del);
	return k;
}
void BFS(NODE *head,NODE *tail){
	visit[st.x][st.y][0] = 1;
	push(head,st);
	while(head->next!=tail){
		XY v = pop(tail);
		for(int q=0;q<4;q++){
			int dx_ = v.x + dx[q];
			int dy_ = v.y + dy[q];
			if(dx_<0||dx_>=end.x||dy_<0||dy_>=end.y)continue;
			if(bk==v.bk_num && map[dx_][dy_] == '1')continue;
			if(map[dx_][dy_]=='1'){
				if(!v.day){
					XY tmp = {dx_,dy_,v.bk_num+1,v.day};
				if(visit[dx_][dy_][tmp.bk_num]!=0&&visit[dx_][dy_][tmp.bk_num]<=visit[v.x][v.y][v.bk_num]+2)
					continue;
				visit[tmp.x][tmp.y][tmp.bk_num] = visit[v.x][v.y][v.bk_num]+2;
				push(head,tmp);
				}else{
				XY tmp = {dx_,dy_,v.bk_num+1,!v.day};
				if(visit[dx_][dy_][tmp.bk_num]!=0&&visit[dx_][dy_][tmp.bk_num]<=visit[v.x][v.y][v.bk_num]+1)
					continue;
				visit[tmp.x][tmp.y][tmp.bk_num] = visit[v.x][v.y][v.bk_num]+1;
				push(head,tmp);
				}
			}else{
				XY tmp = {dx_,dy_,v.bk_num,!v.day};
				if(visit[tmp.x][tmp.y][tmp.bk_num]!=0&&visit[tmp.x][tmp.y][tmp.bk_num]<=visit[v.x][v.y][v.bk_num]+1)
					continue;
				visit[tmp.x][tmp.y][tmp.bk_num] = visit[v.x][v.y][v.bk_num]+1;
				push(head,tmp);
			}
		}
	}
}

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

문제

문제

출처

ICPC

진짜 다 맞는거 같은데 바로틀리네요 반례부탁드립니다ㅠ

jms020820 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말