글 읽기 - 음 .. 코드가 틀렸나봐요 ..

pch1623 4년 전 0

코드를 계속 살펴보아도 제 가 생각한 논리선에서는 다맞는거 같은데 .. 논리가 잘못된것일가요 .. .피드백 부탁드립니다 ...ㅠ

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;


int visited[310][310];
int map[310][310];
int I, s1, s2, d1, d2;
int result = 0;
queue<pair<int, int>> q;
void BFS(int a,int b) {

	q.push(make_pair(a+5, b+5));
	visited[a+5][b+5]=1;
	
	while (!q.empty()) {
		int qSize = q.size();

		for (int i = 0; i < qSize; i++) {
			
			pair<int, int> x = q.front();
			a = x.first;
			b = x.second;
			q.pop();

			if (a == d1 + 5 && b == d2 + 5) return;

			if (!visited[a + 1][b + 2] && map[a + 1][b + 2]) {
				q.push(make_pair(a + 1, b + 2));
				visited[a + 1][b + 2] = 1;
				
				
			}//1 2
			if (!visited[a + 2][b + 1] && map[a + 2][b + 1]) {
				q.push(make_pair(a + 2, b + 1));
				visited[a + 2][b + 1] = 1;
				
			}//2 1
			if (!visited[a - 1][b + 2] && map[a - 1][b + 2]) {
				q.push(make_pair(a - 1, b + 2));
				visited[a - 1][b + 2] = 1;
				
			}//-1 2
			if (!visited[a - 2][b + 1] && map[a - 2][b + 1]) {
				q.push(make_pair(a - 2, b + 1));
				visited[a - 2][b + 1] = 1;
				
			}//-2 1
			if (!visited[a + 1][b - 2] && map[a + 1][b - 2]) {
				q.push(make_pair(a + 1, b - 2));
				visited[a + 1][b - 2] = 1;
				
			}//1 -2
			if (!visited[a + 2][b - 1] && map[a + 2][b - 1]) {
				q.push(make_pair(a + 2, b - 1));
				visited[a + 2][b - 1] = 1;
				
			}//2 -1
			if (!visited[a - 1][b - 2] && map[a - 1][b - 2]) {
				q.push(make_pair(a - 1, b - 2));
				visited[a - 1][b - 2] = 1;
				
			}//-1 -2
			if (!visited[a - 2][b - 1] && map[a - 2][b - 1]) {
				q.push(make_pair(a - 2, b - 1));
				visited[a - 2][b - 1] = 1;
				
			}//-2 -1
		}
		result++;
	}

}

void reset() {
	for (int i = 5; i < I+5; i++) {
		for (int j = 5; j < I+5; j++) {
			visited[i][j] = 0;
		}
	}
	int qSize = q.size();
	for (int i = 0; i < qSize; i++) {
		q.pop();
	}
	result = 0;
}
void create_map() {
	for (int i = 5; i < I+5; i++) {
		for (int j = 5; j < I+5; j++) {
			map[i][j] = 1;
		}
	}
}
int main() {
	int T;
	cin >> T;
	
	for (int i = 0; i < T; i++) {
		
		cin >> I >>s1 >> s2 >> d1 >> d2;
		
		create_map();
		
		BFS(s1,s2);
		cout << result << "\n";
		reset();
	}



}

seecimi 4년 전 2

도움이 될까 싶어서 답변드립니다.

1. BFS함수 안에서, 좌표 a,b가 map배열의 범위를 넘어가는지에 대한 체크가 이루어 지지 않고 있는데, 이점을 고려하셨나요?

2. 좌표에 일일히 +2, -1 처리를 하실경우, 실수를 하실 가능성이 높아집니다.(코드가 길어지므로) 아래의 방법을 사용하시면 좋을듯 싶습니다.

3. 함수의 인자가 a,b인데, BFS함수 내부에서 다른 int를 가리키는 변수 a,b가 또 사용됩니다. 마찬가지로 실수의 가능성이 높아지므로, 다른 변수이름을 택하시는걸 추천드립니다.

// 상 우상 우 우하 하 좌하 좌 좌상
int dy[] = {1,1,0,-1,-1,-1,0,1};
int dx[] = {0,1,1,1,0,-1,-1,-1};

///////////////////////////////////
    pair<int, int> x = q.front();
			now_x = x.first;
			now_y = x.second;
			q.pop();
    
        for(int i = 0; i < 8; i++)
        {
            int next_x = now_x + dx[i];
            int next_y = now_y + dy[i];
            
            if(0 <= next_x && next_x < l && 0 <= next_y && next_y < l)
                if(!visited[next_x][next_y] && map[next_x][next_y]) {
				    q.push(make_pair(next_x, next_y));
				    visited[next_x][next_y] = 1;
        }

seecimi 4년 전 2

dy,dx 원소들이 틀려서 다시 올립니다.

int dy[] = {2,1,-1,-2,-2,-1,1,2};
int dx[] = {1,2,2,1,-1,-2,-2,-1};

pch1623 4년 전 1

소중한 댓글 너무 감사 드립니다. 제가 코드를 수정해보았는데 답이좀 다르게 나와가지고 .. 코드가 어렵진 않아서 이해는 되는거같은데 지금 수정한 코드가 조금 잘못되었을까요 ?? 시간나실때 봐주시면 너무 감사하겠습니다 .

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;

int dy[] = { 2,1,-1,-2,-2,-1,1,2 };
int dx[] = { 1,2,2,1,-1,-2,-2,-1 };
int visited[310][310];
int map[310][310];
int I, s1, s2, d1, d2;
int result = 0;
queue<pair<int, int>> q;

void BFS(int a, int b) {

	q.push(make_pair(a , b));
	visited[a][b] = 1;

	while (!q.empty()) {
		int qSize = q.size();

		for (int j = 0;j < qSize; j++) {
			pair<int, int> x = q.front();
			int now_x = x.first;
			int now_y = x.second;
			q.pop();

			if (a == d1 && b == d2 ) return;
			for (int i = 0; i < 8; i++)
			{
				int next_x = now_x + dx[i];
				int next_y = now_y + dy[i];

				if (0 <= next_x && next_x < I && 0 <= next_y && next_y < I){
					if (!visited[next_x][next_y] && map[next_x][next_y]) {
						q.push(make_pair(next_x, next_y));
						visited[next_x][next_y] = 1;
					}
			}
		}
		}
			result++;


	}
}

void reset() {
	for (int i = 0; i < I; i++) {
		for (int j = 0; j < I; j++) {
			visited[i][j] = 0;
		}
	}
	int qSize = q.size();
	for (int i = 0; i < qSize; i++) {
		q.pop();
	}
	result = 0;
}

void create_map() {
	for (int i = 0; i < I; i++) {
		for (int j = 0; j < I; j++) {
			map[i][j] = 1;
		}
	}
}

int main() {
	int T;
	cin >> T;
	
	for (int i = 0; i < T; i++) {
		
		cin >> I >>s1 >> s2 >> d1 >> d2;
		
		create_map();
		
		BFS(s1,s2);
		cout << result << "\n";
		reset();
	}
}

seecimi 4년 전 2

29번째 줄만 잘 보시면 될 것 같아요^^~

pch1623 4년 전 2

부끄럽고 너무 감사합니다 . 코로나 조심하시고 행복한 하루되세요 !

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

문제

문제

출처

ICPC

음 .. 코드가 틀렸나봐요 ..

pch1623 4년 전 0

seecimi 4년 전 2

seecimi 4년 전 2

pch1623 4년 전 1

seecimi 4년 전 2

pch1623 4년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말