글 읽기 - 반례를 못찾겠습니다.

kookisung 3년 전 0

질문검색에 있는 반례로 테스트한 결과 정상적으로 작동합니다..

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <queue>

using namespace std;

typedef struct node{
	int x;
	int y;
	int count;
}Node;

Node inputNode(int x, int y, int count);
void bfs(int N, int M);


int arr[1001][1001];
int visited[1001][1001][2];
bool is_inside(int _ny, int _nx, int N, int M) {
	return (_ny >= 1 && _ny <= N && _nx >= 1 && _nx <= M);
}

int main()
{
	int N, M, i, j;

	freopen("input.txt", "r", stdin);
	cin >> N >> M;

	for(i = 1; i <= N; i++){
		for(j = 1; j <= M; j++){
			scanf("%1d", &arr[i][j]);
		}
	}

	bfs(N, M);

}

Node inputNode(int x, int y, int count){
	Node node;

	node.x = x;
	node.y = y;
	node.count = count;

	return node;
}

void bfs(int N, int M){
	queue<Node> myQ;
	Node node;
	Node tmp;
	int i, j, tmpX, tmpY, tmpCount;
	int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

	node = inputNode(1, 1, 1);
	visited[1][1][1] = 1;
	myQ.push(node);

	while(myQ.size() != 0){
		node = myQ.front();
		myQ.pop();
		tmpCount = node.count;
		if(node.x == N && node.y == M){
			cout << visited[N][M][node.count] << "\n";
			return;
		}

		for(i = 0; i < 4; i++){
			tmpX = node.x+dir[i][0];
			tmpY = node.y+dir[i][1];

			if(is_inside(tmpX, tmpY, N, M)){
				if(arr[tmpX][tmpY] == 0 && visited[tmpX][tmpY][tmpCount] == 0){
					visited[tmpX][tmpY][tmpCount] =
						visited[node.x][node.y][tmpCount]+1;
					tmp = inputNode(tmpX, tmpY, tmpCount);
					myQ.push(tmp);
				}
				if(arr[tmpX][tmpY] == 1 && tmpCount){
					if(tmpCount == 1){
						visited[tmpX][tmpY][tmpCount-1] =
							visited[node.x][node.y][tmpCount]+1;
						tmp = inputNode(tmpX, tmpY, tmpCount-1);
						myQ.push(tmp);
					}
				}
			}

		}	

	}
	cout << "-1" << "\n";
}

mwy3055 3년 전 0

코드 잘 작성하셨습니다.

28번 줄만 지워 보세요. ㅋㅋㅋㅠㅠ

kookisung 3년 전 0

하....바로 되네요...제가 저때 멘탈이 많이 나갔었나바요....ㅜㅜㅜ 감사합니당...

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

문제

문제

출처

ICPC

반례를 못찾겠습니다.

kookisung 3년 전 0

mwy3055 3년 전 0

kookisung 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말