글 읽기 - 반례 요청드립니다.

thankyouoov 5년 전 0

질문 게시판에 올라와있는 모든 테스트케이스 통과하는데 제출하면 실패네요

visit / visited 배열 각각 두개 선언해서 진행했습니다

코드는 급하게 복붙하느라 if 조건문 안에 필요없는 부분도 있습니다..

#include<iostream>
#include<queue>

using namespace std;

int N, M;
bool map[1000][1000];
bool bb[1000][1000];
bool visit[1000][1000];
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int ans;
struct pos {
	int x;
	int y;
	bool v;
	int d;
	pos(int xx, int yy, int vv, int dd) {
		x = xx; y = yy; v = vv; d = dd;
	}
};
queue<pos> q;


bool is_bound(int x, int y) {
	return x >= 0 && x < N && y >= 0 && y < M;
}
void bfs() {
	q.push(pos(0, 0, 0, 1));
	
	while (!q.empty()) {
		int xx = q.front().x;
		int yy = q.front().y;
		bool vv = q.front().v;
		int dd = q.front().d;
		q.pop();
		
		visit[xx][yy] = 1;
		//cout << xx << " " << yy <<" "<<vv<<" "<<dd <<endl;
		if (xx == N - 1 && yy == M - 1) {
			ans = dd;
			return;
		}
		for (int i = 0; i < 4; ++i) {
			int px = xx + dx[i];
			int py = yy + dy[i];
			if (is_bound(px, py)) {
				if (!visit[px][py]) {
					if (vv && map[px][py])
						continue;
					if (map[px][py]) {
						q.push(pos(px, py, 1, dd + 1));
						bb[px][py] = 1;
					}
					else {
						q.push(pos(px, py, vv, dd + 1));
						bb[px][py] = vv;
					}
					visit[px][py] = 1;
				}
				else {
					if (bb[px][py] == vv || bb[px][py] == 0) {
						continue;
					}
					else {
						if (vv && map[px][py])
							continue;
						if (map[px][py]) {
							q.push(pos(px, py, 1, dd + 1));
							bb[px][py] = 1;
						}
						else {
							q.push(pos(px, py, vv, dd + 1));
							bb[px][py] = vv;
						}
						visit[px][py] = 1;
					}
				}
			}
		}
	}
	ans = -1;
}

int main() {

	freopen("input.txt", "r", stdin);
	scanf("%d %d", &N, &M);

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

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

문제

문제

출처

ICPC

반례 요청드립니다.

thankyouoov 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말