글 읽기 - 이게 왜 틀린거죠?? ㅠㅠㅠㅠㅠㅠ

chrisjc 7년 전 0

하루종일 찾는데 도저히 모르겠네요...

큐의 크기며 .. 뭐며...

반례나 이유좀 알려주세요 ㅠㅠ

BFS를 이용해서 구현했습니다.

#include <iostream>
#include <string.h>
#include <algorithm>
#include <functional>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
class point
{
public:
	int x;
	int y;
};
// 정점이 더작은 것부터 방문
int graph[2000][2000] = { 0, };
int visit[2000][2000] = { 0, };
int xstep[4] = {-1,1,0,0};
int ystep[4] = {0,0,-1,1};
point* queue[100000];
int maxsize = 100000;
class userq
{
public:
	int rear;
	int front;
	int maxsize;
	int size;
};


void DFS(int vertex);

void BFS(point* v, userq* userqueue);
userq* init();
int isempty(userq* userq);
int isfull(userq* userq);
void enqueue(userq* userq, point* data);
point* dequeue(userq* userq);
int n, m, v;
int okstep(int x, int y);
int main() {
	// n 이 와이값

	cin >> n >> m;
	cin.ignore();
	if (!((n >= 2) && (n <= 100) && (m >= 2) && (m <= 100)))
		return 0;

	for (int i = 0; i < n; i++)
	{
		char temp[100];
		cin.getline(temp,100);
		for (int j = 0; j < m; j++)
		{
			
			graph[j][i] = temp[j] - '0';
		}
	}
	
	point start;
	start.x = 0;
	start.y = 0;

	userq* temp = init();

	BFS(&start, temp);


	cout << visit[m - 1][n - 1] << endl;
	

	

}

userq* init()
{
	userq *temp = (userq*)malloc(sizeof(userq));
	temp->maxsize = maxsize;
	temp->size = 0;
	temp->front = 0;
	temp->rear = 0;

	return temp;
}

int isempty(userq* userq)
{
	if (userq->front == userq->rear)
		return 1;
	else
		return 0;
}
int isfull(userq* userq)
{

	if ((userq->rear+1) % maxsize == userq->front)
		return 1;
	else
		return 0;
}
void enqueue(userq* userq,point* data)
{
	if (isfull(userq) == 1)
		return;

	userq->rear = (userq->rear + 1) % maxsize;
	queue[userq->rear] = data;
}
point* dequeue(userq* userq)
{
	if (isempty(userq) == 1)
		return 0;

	userq->front = (userq->front + 1) % maxsize;
	return queue[userq->front];
}


int okstep(int x, int y)
{
	if ((y>n-1) || (y<0) ||(x<0) || (x>m-1))
	{
	

		return -1;
	}
	if (visit[x][y] >= 1)
	{
		return -1;
	}

	if (graph[x][y] == 0)
	{
		
		return -1;
	}
	return 1;
}

void BFS(point* v, userq* userqueue)
{
	visit[v->x][v->y] = 1;

	enqueue(userqueue, v);
	
	while (isempty(userqueue) != 1)
	{
		point* v1 = dequeue(userqueue);
			
		for (int i = 0; i < 4; i++)
		{
			int newx, newy;
			newx = v1->x + xstep[i];
			newy = v1->y + ystep[i];
		

			if (okstep(newx, newy)==1)
			{
				
				point* temp = (point*)malloc(sizeof(point));
				temp->x = newx;
				temp->y = newy;

				visit[newx][newy] = visit[v1->x][v1->y]+1;
			
				enqueue(userqueue, temp);

			}

		}
		}
	}

chrisjc 7년 전 0

이럴수가.... 맨위에 입력부분에서 100개 를 받을경우 char a[100] 여기서 마지막 널 문자까지 받아야 되기 때문에

[101]로 선언 해줘서 해결했습니다...

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

문제

문제

출처

ICPC

이게 왜 틀린거죠?? ㅠㅠㅠㅠㅠㅠ

chrisjc 7년 전 0

chrisjc 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말