글 읽기 - 36%에서 자꾸 틀립니다.. 반례를 모르겠습니다.

lsh9159 7년 전 0

질문게시판에 올라온 tc는 다맞는데 도저히 어디서 틀렸는지 모르겠습니다.

도와주세요 ㅠㅜㅜ

#include<cstdio>
#include<queue>
#include<tuple>
#include<algorithm>
using namespace std;
int start = 100, m[10] = { 0,1,2,3,4,5,6,7,8,9 }, des, n;
bool visit[10001000] = { false, };
int main() {
	scanf("%d%d", &des, &n);
	if (des == 100) {
		printf("0");
		return 0;
	}

	for (int i = 0; i < n; i++) {
		int a; scanf("%d", &a);
		m[a] = 10;
	}

	sort(m, m + 10);
	queue<tuple<int, int, int>> q;

	for (int i = 0; i < 10 - n; i++) {
		q.push(make_tuple(m[i], 1, 0));
		if (des == m[i]) {
			printf("1");
			return 0;
		}
		visit[m[i]] = true;
	}

	q.push(make_tuple(101, 1, 1));
	q.push(make_tuple(99, 1, 1));
	if (des == 101 || des == 99) {
		printf("1"); return 0;
		visit[101] = visit[99] = true;
	}

	while (!q.empty()) {
		int curValue = get<0>(q.front());
		int level = get<1>(q.front());
		int check = get<2>(q.front());
		q.pop();

		if (check == 0) { //이전에 누른 번호가 숫자였을 때
			for (int i = 0; i < 10 - n; i++) {
				if (visit[curValue * 10 + m[i]] == false && curValue * 10 + m[i]<1000000) {
					if (curValue * 10 + m[i] == des) {
						printf("%d", level + 1);
						return 0;
					}
					q.push(make_tuple(curValue * 10 + m[i], level + 1, 0));
					visit[curValue * 10 + m[i]] = true;
				}
			}

			if (visit[curValue + 1] == false && visit[curValue + 1]<500000) {
				if (curValue + 1 == des) {
					printf("%d", level + 1);
					return 0;
				}
				q.push(make_tuple(curValue + 1, level + 1, 1));
				visit[curValue + 1] = true;
			}

			if (visit[curValue - 1] == false && curValue - 1 >= 0) {
				if (curValue - 1 == des) {
					printf("%d", level + 1);
					return 0;
				}
				q.push(make_tuple(curValue - 1, level + 1, 1));
				visit[curValue - 1] = true;
			}
		}

		else { //이전에 누른 것이 +,-일때
			for (int i = 0; i < 10 - n; i++) {
				if (visit[m[i]] == false) {
					if (m[i] == des) {
						printf("%d", level + 1);
						return 0;
					}
					q.push(make_tuple(m[i], level + 1, 0));
					visit[m[i]] = true;
				}
			}

			if (visit[curValue + 1] == false && visit[curValue + 1]<500000) {
				if (curValue + 1 == des) {
					printf("%d", level + 1);
					return 0;
				}
				q.push(make_tuple(curValue + 1, level + 1, 1));
				visit[curValue + 1] = true;
			}

			if (visit[curValue - 1] == false && curValue - 1 >= 0) {
				if (curValue - 1 == des) {
					printf("%d", level + 1);
					return 0;
				}
				q.push(make_tuple(curValue - 1, level + 1, 1));
				visit[curValue - 1] = true;
			}
		}
	}

}

naong606 7년 전 1

1020

입력하면 4가 나와야 하는데 5가 나오네요

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

문제

문제

출처

ICPC

36%에서 자꾸 틀립니다.. 반례를 모르겠습니다.

lsh9159 7년 전 0

naong606 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말