글 읽기 - 1445 일요일 아침의 데이트 틀렸습니다 뜨네요 ㅠㅠ

huhmin 8년 전 0

기본bfs 방식 이용해서 풀었는데요.

틀렸습니다가 뜨는데 이유를 모르겠어요ㅠㅠ

visit 배열을 두 개를 둬서 하나는 쓰레기 통과한 거 저장해놓고 나머지 하나는 쓰레기 옆에 지나간 횟수 저장해놨어요

앞으로 갈 칸이 현재 지나온 쓰레기 칸과 동일하면 쓰레기 옆에 지나간 횟수가 적을 때에만

큐에 넣도록 했어요..

어디가 틀렸을까요 ㅠㅠ 알려주셉요ㅠㅠ

아 그리고 S,F 일때는 횟수를 세지 않는다고 해서 front가 1이 넘을 때에 그 칸 주변에 쓰레기가 있으면 옆으로 지나간 칸 +1 하고

없으면 그냥 유지하도록 했어요!

#include <stdio.h>
#define INF 987654321;
int visit[51][51];
int visit2[51][51];
int garo, sero;
char map[51][51];
int dx[] = { 0, 0, -1, 1 };
int dy[] = { 1, -1, 0, 0 };
typedef struct{
	int x;
	int y;
	int direct;
	int side;
}data;
data arr[50000];
int front, rear;
int fx, fy, ans1, ans2;
void init(){
	for (int i = 0; i < 51; i++){
		for (int j = 0; j < 51; j++){
			visit[i][j] = visit2[i][j] = INF;
		}
	}
	front = rear = 0;
	ans1 = ans2 = INF;
}
void bfs(){
	while (1){
		if (front == rear)break;
		int sx = arr[front].x;
		int sy = arr[front].y;
		int through = arr[front].direct;
		int beside = arr[front++].side;
		if (map[sx][sy] == 'F'){
			if (ans1 > through){
				ans1 = through;
				ans2 = beside;
			}
			else if (ans1 == through){
				if (ans2 > beside){
					ans2 = beside;
				}
			}
			continue;
		}
		if (front > 1){
			for (int i = 0; i < 4; i++){
				int tx = sx + dx[i];
				int ty = sy + dy[i];
				if (tx < 0 || ty < 0 || tx >= garo || ty >= sero)continue;
				if (map[tx][ty] == 'g'){
					beside++;
					break;
				}
			}
		}
		for (int i = 0; i < 4; i++){
			int tx = sx + dx[i];
			int ty = sy + dy[i];
			if (tx < 0 || ty < 0 || tx >= garo || ty >= sero)continue;
			if (map[tx][ty] == 'g'){
				if (visit[tx][ty] > through + 1){
					visit[tx][ty] = through + 1;
					visit2[tx][ty] = beside;
					arr[rear].x = tx;
					arr[rear].y = ty;
					arr[rear].direct = through + 1;
					arr[rear++].side = beside;
				}
				else if (visit[tx][ty] == through + 1){
					if (visit2[tx][ty] > beside){
						visit2[tx][ty] = beside;
						arr[rear].x = tx;
						arr[rear].y = ty;
						arr[rear].direct = through + 1;
						arr[rear++].side = beside;
					}
				}
			}
			else {
				if (visit[tx][ty]>through){
					visit[tx][ty] = through;
					visit2[tx][ty] = beside;
					arr[rear].x = tx;
					arr[rear].y = ty;
					arr[rear].direct = through;
					arr[rear++].side = beside;
				}
				else if (visit[tx][ty] == through){
					if (visit2[tx][ty] > beside){
						visit2[tx][ty] = beside;
						arr[rear].x = tx;
						arr[rear].y = ty;
						arr[rear].direct = through;
						arr[rear++].side = beside;
					}
				}
			}
		}
	}
}
int main(){
	freopen("input.txt", "r", stdin);
	init();
	scanf("%d %d", &garo, &sero);
	for (int i = 0; i < garo; i++){
		scanf("%s", &map[i]);
	}
	int t = 0;
	for (int i = 0; i < garo; i++){
		for (int j = 0; j < sero; j++){
			if (map[i][j] == 'S'){
				fx = i;
				fy = j;
				t = 1;
				break;
			}
		}
		if (t)break;
	}
	visit[fx][fy] = 0;
	visit2[fx][fy] = 0;
	arr[rear].x = fx;
	arr[rear].y = fy;
	arr[rear].direct = 0;
	arr[rear++].side = 0;
	bfs();
	printf("%d %d\n", ans1, ans2);
	return 0;
}

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

문제

문제

출처

ICPC

1445 일요일 아침의 데이트 틀렸습니다 뜨네요 ㅠㅠ

huhmin 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말