글 읽기 - 벽부수는걸 어떻게 처리해야할지 감이안잡힙니다.ㅠㅠ

may900515 7년 전 0

좀 도와주십셔 ㅠㅠ

그냥 최단거리를 찾는건 이제 숙지가 되어서 알겠습니다만 벽을 부순다는 찬스를 쓰는거에서 어떻게 해야할지가 막막합니다..

헬프해주십시오 고수님들!!

#include<stdio.h>


struct qu {

	int x[100];
	int y[100];
	int l[100];
}qu;


char map[1010][1010];
int visit[1010][1010];
int N, M;
int pos , cnt ;
int result;

int enque(int w, int v, int k) {

	visit[w][v] = 1;
	qu.y[cnt] = w;
	qu.x[cnt] = v;
	qu.l[cnt] = k;
	
	cnt++;
	return 0;
}


int bfs() {

	enque(0, 0, 0);

	while (pos < cnt) {
		 
		if (visit[qu.y[pos] + 1][qu.x[pos]] != 1 && map[qu.y[pos]+1][qu.x[pos]] == '0')
		
			enque(qu.y[pos] + 1,qu.x[pos], qu.l[pos] + 1);
		
		if (visit[qu.y[pos] - 1][qu.x[pos]] != 1 && map[qu.y[pos]-1][qu.x[pos]] == '0')
			
			enque(qu.y[pos] - 1,qu.x[pos], qu.l[pos] + 1);
		
		if (visit[qu.y[pos]][qu.x[pos] + 1] != 1 && map[qu.y[pos]][qu.x[pos]+1] == '0')
			
			enque(qu.y[pos],qu.x[pos] + 1, qu.l[pos] + 1);
		
		if (visit[qu.y[pos]][qu.x[pos] - 1] != 1 && map[qu.y[pos]][qu.x[pos]-1] == '0')
			
			enque(qu.y[pos],qu.x[pos] - 1, qu.l[pos] + 1);

		
		pos++;
	}
	result = qu.l[pos - 1] + 1;

	 printf("%d\n", result );
	return 0;
}



int main(void) {

	scanf("%d%d", &N, &M);
	 
	 for (int i = 0; i < N; i++)
			scanf("%s", &map[i] );
 
	 printf("\n");
	 bfs();
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++)
			printf("%d", visit[i][j]);
		printf("\n");
	}
	
	 
	return 0;
}

sksdong1 7년 전 2

다익스트라 개념을 도입해서

벽을 만나면 가중치를 1로 두고 우선순위 큐에 담아요. 0의 가중치로 목적지에 도달 못하면

1의 가중치로 선정된 위치 ( 벽의 위치)부터 도달이 가능한지 여부를 파악하면 될 것 같습니다.

뭐 물론 벽이 여러개면 가중치값이 2,3 늘어나구요

yclock 7년 전 2

먼저 BFS를 두 번 돌겁니다.

처음 BFS는 시작점에서 출발하고, 두 번째 BFS는 도착점에서 출발합니다.

이 행위를 통해 우리는 모든 칸에 대해서, "벽을 뚫지 않았을 때, '시작점과의 거리'와 '도착점과의 거리'"를 알 수 있습니다.

이제 모든 '벽'을 차례대로 보면서, 이 칸을 뚫고 지나갈 때의 최단거리를 다음과 같이 계산할 수 있습니다.

(거리) = min{ (이웃한 어떤 칸의 '시작점과의 거리') + (이웃한 어떤 칸의 '도착점과의 거리') }

yclock 7년 전 1

방금 제 소스를 보고 왔습니다.

BFS 한 번만 돌려서도 풀 수 있습니다.

Queue에 "현재 칸의 좌표"와 "여기까지 오면서 벽을 뚫었는 지의 여부", "거리" 정보를 같이 집어넣습니다.

~~이제, "벽을 뚫은 적이 있는지의 여부"에 따라서, 잘 돌리면 됩니다.....~~

may900515 7년 전 1

yclock

sksdong1

두분다 감사합니다.ㅜ

ㅜㅜ 원초적인 결함이.. 벽을 뚫는다는건 1이라는 자리를 0으로 바꿔줘야하는건가요? 아니면 1을 한번 지나갈수 있다고 설정을 해야할까요??

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

문제

문제

출처

ICPC

벽부수는걸 어떻게 처리해야할지 감이안잡힙니다.ㅠㅠ

may900515 7년 전 0

sksdong1 7년 전 2

yclock 7년 전 2

yclock 7년 전 1

may900515 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말