글 읽기 - 틀린 테스트 케이스를 찾지 못하겠습니다 ㅠㅠㅠ

thsdndqo 7년 전 1

어느 테스트케이스에 틀린건지 찾지 못하겠습니다ㅠㅠㅠㅠ

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <iostream>
using namespace std;
int map[52][52];
int dp[52][52];
int N_x, N_y;

//dp 값을 100으로 초기 setting 해놓고 max 값을 비교할때 if(dp[x][y] != 100) temp=max(temp, dp[x][y])
int search(int x, int y)
{
	dp[x][y] = 0;
	int total = 0;
	int temp_max = 0;
	int temp_x, temp_y;

	queue<int> que_x;
	queue<int> que_y;

	que_x.push(x);
	que_y.push(y);

	while (que_x.size() != 0)
	{
		temp_x = que_x.front();
		temp_y = que_y.front();

		que_x.pop();
		que_y.pop();

		if ((map[temp_x-1][temp_y] == 1) &&(dp[temp_x-1][temp_y] > dp[temp_x][temp_y]+1)) //상
		{
			//갈 수 있는 길이고 그 길로 가는 최단거리가 지금 가는 길의 경우보다 클 경우.
			que_x.push(temp_x - 1);
			que_y.push(temp_y);

			dp[temp_x - 1][temp_y] = dp[temp_x][temp_y] + 1;

			temp_max = max(temp_max, dp[temp_x - 1][temp_y]);
		}
		if ((map[temp_x + 1][temp_y] == 1) && (dp[temp_x + 1][temp_y] > dp[temp_x][temp_y] + 1)) //하
		{
			//갈 수 있는 길이고 그 길로 가는 최단거리가 지금 가는 길의 경우보다 클 경우.
			que_x.push(temp_x + 1);
			que_y.push(temp_y);

			dp[temp_x + 1][temp_y] = dp[temp_x][temp_y] + 1;

			temp_max = max(temp_max, dp[temp_x + 1][temp_y]);
		}
		if ((map[temp_x][temp_y -1 ] == 1) && (dp[temp_x ][temp_y -1 ] > dp[temp_x][temp_y] + 1)) //좌
		{
			//갈 수 있는 길이고 그 길로 가는 최단거리가 지금 가는 길의 경우보다 클 경우.
			que_x.push(temp_x);
			que_y.push(temp_y -1 );

			dp[temp_x][temp_y -1 ] = dp[temp_x][temp_y] + 1;

			temp_max = max(temp_max, dp[temp_x][temp_y -1 ]);
		}
		if ((map[temp_x][temp_y +1 ] == 1) && (dp[temp_x][temp_y +1] > dp[temp_x][temp_y] + 1)) //우
		{
			//갈 수 있는 길이고 그 길로 가는 최단거리가 지금 가는 길의 경우보다 클 경우.
			que_x.push(temp_x);
			que_y.push(temp_y+1);

			dp[temp_x][temp_y+1] = dp[temp_x][temp_y] + 1;

			temp_max = max(temp_max, dp[temp_x][temp_y +1 ]);
		}
		
	}
	for (int i = 0; i < N_x + 1; i++)
	{
		for (int j = 0; j < N_y + 1; j++)
		{
			dp[i][j] = 100;
		}
	}
	
	return temp_max;
}

int main()
{
	memset(map, 0, sizeof(map));

	
	char c;
	int max_num=0;
	scanf("%d %d", &N_x, &N_y);
	for (int i = 0; i < N_x + 1; i++)
	{
		for (int j = 0; j < N_y + 1; j++)
		{
			dp[i][j] = 100;
		}
	}
	cin.ignore(999, '\n');

	//입력받기, L=1, W=0
	for (int i = 1; i < N_x + 1; i++)
	{
		for (int j = 1; j < N_y + 1; j++)
		{
			scanf("%1c", &c);
			if (c == 'W')
			{
				map[i][j] = 0;
			}
			else
			{
				map[i][j] = 1;
			}
		}
		cin.ignore(999, '\n');

	}

	for (int i = 1; i < N_x + 1; i++)
	{
		for (int j = 1; j < N_y + 1; j++)
		{
			if (map[i][j]== 1)
			{
				max_num = max(max_num, search(i, j));
			}
		}
	}

	printf("%d", max_num);
	return 0;
}

rptdpavm 7년 전 0

그러게요... 힘내세요

methylene 7년 전 0

dp 초기값이 너무 작은 것 같네요 길이 뻥 뚫린 지도상이라면 100으로 잡아도 충분하겠지만,

W로 막혀서 길이 구불 구불하게 형성될 수도 있기 때문에 그냥 넉넉하게 2500으로 잡으세요 어차피 그렇게한다고 메모리 더 먹는 것도 아니니까...

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

문제

문제

출처

ICPC

틀린 테스트 케이스를 찾지 못하겠습니다 ㅠㅠㅠ

thsdndqo 7년 전 1

rptdpavm 7년 전 0

methylene 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말