글 읽기 - 차라리 시간초과면 좋겠습니다.. 왜 틀리는 건지 전혀 감이 안잡힙니다..

ploffer11 5년 전 4

게시판에서 찾은 반례들과 제가 적당히 만든 예시들 모두 잘 나오지만 제출하면 바로 틀립니다..

도와주실분을 찾습니다 ㅜㅜ 주석열심히 써놓았습니다.

#include <iostream>
#include <tuple>
#include <queue>
#include <string>
#include <algorithm>
#include <map>
using namespace std;
typedef pair<int, int> pii;
typedef tuple<int, int, int> t;

int n, m, ans;
string inp;

int matrix[100][100];
int dr[] = { 1, -1, 0, 0 }, dc[] = { 0, 0, 1, -1 };

map<string, bool> visit;

// 범위체크 or matrix에 구멍이 있는지 확인합니다 (구멍이 있는경우 0)
bool chk(int r, int c)
{
	return 1 <= r && r <= n && 1 <= c && c <= m && matrix[r][c];
}

// visit체크를 map으로 하기 위한 적절한 converter입니다.
// r, c 에서 R, C로 방문했다면 "r,c,R,C"라는 string을 key로 사용합니다. 
string converter(int r, int c, int R, int C)
{
	return (to_string(r) + "," + to_string(c)
			+ "," + to_string(R) + "," + to_string(C));
}

int bfs()
{
	int ans = 0;
    // q는 튜플을 받으며, (depth, r, c) 로 저장을 합니다.
	queue<t> q;
    // 초기 depth : 1, (r,c) = (1,1) 이므로 (1,1,1)
	q.push(t(1, 1, 1));

	while ( !q.empty() )
	{
        // c++ 17 확장 문법
		auto[depth, r, c] = q.front();
		ans = max(ans, depth);
		q.pop();


		for ( int i = 0; i < 4; i++ )
		{
            // 몇 칸 이동할 지 정합니다. 
            // matrix[r][c] 에는 숫자가 담겨있습니다.
			int R = r + dr[i] * matrix[r][c];
			int C = c + dc[i] * matrix[r][c];
            
            // 범위체크와 구멍이 있는지 여부를 chk함수가 해줍니다.
			if ( chk(R, C) )
			{
                // 만약 r,c(시작) 에서 R,C(도착) 으로 간 적이 있다면
                // -1을 리턴합니다 (싸이클이 생긴 것)
				if ( visit[converter(r, c, R, C)] ) return -1;
				else
				{
                    // r,c -> R,C 로 간 적이 없다면 방문 표시 후
                    // 큐에 넣습니다.
					visit[converter(r, c, R, C)] = true;
					q.push(t(depth + 1, R, C));
				}
			}
		}
	}

	return ans;
}

int main()
{
	cin >> n >> m;

	for ( int i = 1; i <= n; i++ )
	{
		cin >> inp;
		for ( int j = 1; j <= m; j++ )
		{
			if ( inp[j - 1] == 'H' )
			{
				continue;
			}

			else
			{
				matrix[i][j] = inp[j - 1] - '0';
			}
		}
	}
	cout << bfs();
}

ploffer11 5년 전 5

이건 게시판 반례와 열심히 만들어 넣은 예시들입니다.

5 7
3994995
9999999
4H99399
9999999
2993994

3 4
3552
5555
2553

4 3
133
5HH
HHH
21H

5 5
4HHH9
HHHHH
HHH12
HHHHH
3HH2H

4 4
12H3
2H3H
HHHH
41H2

5 5
13HH2
2HHHH
HHHH2
HHHHH
3HHH4

5 5
13HH1
HHHH3
3HH2H
HHHHH
2HH31

5 5
4H3H2
HHHHH
HHHHH
HH2HH
1HHH4

5 5
4H3H2
HHHHH
HHHHH
HH2HH
1HHH4

3 3
2H1
3H2
HHH

3 3
2H1
HH2
HHH


3 3
2H1
HH1
HHH

cgiosy 5년 전 10

반례입니다.

6 7
12HHHHH
2214HHH
H1HHHHH
H4H9H2H
HHHHHHH
HHH2HHH

Out: -1
Ans: 7

ploffer11 5년 전 0

와.. 아... 진짜 상상도못한.. ㅜㅜㅜ 미치겠군요

별로 잘 짜지도 않은 코드 읽고 완벽한 반례 주셔서 감사합니다 ..

디버그 열심히 해보겠습니다..

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

문제

문제

출처

ICPC

차라리 시간초과면 좋겠습니다.. 왜 틀리는 건지 전혀 감이 안잡힙니다..

ploffer11 5년 전 4

ploffer11 5년 전 5

cgiosy 5년 전 10

ploffer11 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말