글 읽기 - 제가 작성한 코드의 오류를 모르겠습니다..

(追記) (追記ここまで)

제가 작성한 코드의 오류를 모르겠습니다..

14466번 - 소가 길을 건너간 이유 6

parkgunwon1 1년 전 0

저는 bfs를 탐색하면서 길을 통하지 않고 방문할수 있는 모든 소의 쌍을 result에 담아 두었고 이를 모든 소의 쌍에서 뺌으로서 답을 구하려고 했습니다.

즉 모든 소의 쌍인 (R * ( R - 1) - result) / 2인것인데 이 이론이 잘못된걸까요 아니면 코드에서 오류가 있는걸까요..

go는 길을 저장하여 갈수 없는 곳을 나타내는것입니다

#include<bits/stdc++.h>
#define Fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
using namespace std;
vector<vector<int>> visited;
vector<vector<vector<bool>>> go;
vector<vector<int>> board;
//오른쪽 왼쪽 위 아래
int dir[4][2] = {{0,1},{0,-1},{-1,0},{1,0}};
int result = 0;
int GetDirection(int r1, int c1, int r2, int c2) {
 int r = r1 - r2;
 int c = c1 - c2;
 int dir = 0;
 if (r == 0) {
 if (c < 0) dir = 0;
 else dir = 1;
 }
 else {
 if (r < 0) dir = 3;
 else dir = 2;
 }
 return dir;
}
int main() {
 Fast;
 int n, k, R;
 cin >> n >> k >> R;
 go.resize(n + 1, vector<vector<bool>>(n + 1, vector<bool>(4)));
 board.resize(n + 1, vector<int>(n + 1));
 for (int i = 0; i < k; i++) {
 int r1, c1, r2, c2;
 cin >> r1 >> c1 >> r2 >> c2;
 int dir = GetDirection(r1, c1, r2, c2);
 int reverse = GetDirection(r2, c2, r1, c1);
 go[r1][c1][dir] = true;
 go[r2][c2][reverse] = true;
 }
 for (int i = 0; i < R; i++) {
 int r, c;
 cin >> r >> c;
 board[r][c] = 1;
 }
 for (int i = 1; i <= n; i++) {
 for (int j = 1; j <= n; j++) {
 if (board[i][j] == 1) {
 visited.clear();
 visited.resize(n + 1, vector<int>(n + 1));
 queue<pair<int, int>> s;
 s.push({ i, j });
 visited[i][j] = true;
 while (!s.empty()) {
 pair<int, int> top = s.front();
 s.pop();
 int cur_r = top.first;
 int cur_c = top.second;
 for (int k = 0; k < 4; k++) {
 int next_r = cur_r + dir[k][0];
 int next_c = cur_c + dir[k][1];
 if (next_r <= 0 || next_r > n || next_c <= 0 || next_c > n) continue;
 if (visited[next_r][next_c]) continue;
 if (go[cur_r][cur_c][k]) continue;
 if (board[next_r][next_c] == 1) {
 result++;
 }
 visited[next_r][next_c] = true;
 s.push({ next_r, next_c });
 }
 }
 }
 }
 }
 result = (R * (R - 1) - result) / 2;
 cout << result;
 return 0;
}

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC