글 읽기 - 반례 하나만 들어주시면 감사하겠습니다...

legendmic2 5년 전 0

map이라는 2차원벡터에 입력값을 저장하여

이중포문을 돌려서 길에 해당하는 '.'인 경우 인접한 빌딩이 2개 이상일 때 막다른길이라고 판단하는 방식입니다.

저의 접근방식이 잘못된것인지 궁금합니다ㅠㅠ 많은 도움 부탁드립니다!

#include <iostream>
#include <vector>

using namespace std;

bool blockFunc(vector< vector<char>> map, vector< pair<int, int>> nearNum, int rNum, int cNum, int r, int c) { // 막히면 true
	bool blocked = false; // 막히면 true
	int cnt = 0;
	for (int i = 0; i < r; i++) { // X : 빌딩 // 길 : .

		for (int j = 0; j < c; j++) {
			for (int k = 0; k < nearNum.size(); k++) {
				if (map[nearNum[k].first][nearNum[k].second] == '.') cnt++;
			}
			if (cnt > 2) {
				blocked = true;
				break;
			}
			cnt = 0;
		}
		if (blocked) break;
	}

	return blocked;
}

vector< pair<int, int>> nearFunc(int r, int c, int i, int j) {
	
	vector< pair<int, int>> nearNum = { {r - 1, c}, {r + 1, c}, {r, c - 1}, {r, c + 1} };// 상 하 좌 우

	for (int i = 0; i < nearNum.size(); i++) {
		if (nearNum[i].first < 0 || nearNum[i].first >= r || nearNum[i].second < 0 || nearNum[i].second >= c)
			nearNum.erase(nearNum.begin() + i);
		i--;
	}

	return nearNum;
}

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	
	int r, c;
	cin >> r >> c;

	vector< vector<char>> map(r);
	vector< pair<int, int>> nearNum;
	bool blocked = false;
	for (int i = 0; i < r; i++) {
		map[i].assign(c, NULL);
	}

	for (int i = 0; i < r; i++) { // X : 빌딩 // 길 : .
		for (int j = 0; j < c; j++) {
			cin >> map[i][j];
		}
	}

	for (int i = 0; i < r; i++) { // X : 빌딩 // 길 : .
		for (int j = 0; j < c; j++) {

			if (map[i][j] == '.') {
				nearNum = nearFunc(r, c, i, j);

				if (blockFunc(map, nearNum, i, j, r, c)) {
					blocked = true;
					break;
				}



				nearNum.clear();
				
			}
			else continue;
			
			if (blocked) break;
		}
	}

	if (blocked) cout << "0";
	else cout << "1";

}

jh05013 5년 전 1

"힌트"에 주어져 있는 데이터를 넣어 보세요.

legendmic2 5년 전 0

@jh05013

nearFunc에서 이상하게 돌아가고있더라구요... 그 부분 수정해서 제출해봤더니 그래도 틀렸다고 나오네요ㅠㅠ

힌트에 주어진 데이터는 따로 컴파일해보니 맞혔는데,, 접근방법 자체가 문제일까요?

#include <iostream>
#include <vector>

using namespace std;

bool blockFunc(vector< vector<char>> map, vector< pair<int, int>> nearNum, int rNum, int cNum, int r, int c) { // 막히면 true
	bool blocked = false; // 막히면 true
	int cnt = 0;
	for (int i = 0; i < r; i++) { // X : 빌딩 // 길 : .

		for (int j = 0; j < c; j++) {
			for (int k = 0; k < nearNum.size(); k++) {
				if (map[nearNum[k].first][nearNum[k].second] == '.') cnt++;
			}
			if (cnt > 2) {
				blocked = true;
				break;
			}
			cnt = 0;
		}
		if (blocked) break;
	}

	return blocked;
}

vector< pair<int, int>> nearFunc(int r, int c, int i, int j) {
	
	vector< pair<int, int>> nearNum = { {i - 1, j}, {i + 1, j}, {i, j - 1}, {i, j + 1} };// 상 하 좌 우

	for (int t = 0; t < nearNum.size(); t++) {
		if (nearNum[t].first < 0 || nearNum[t].first >= r || nearNum[t].second < 0 || nearNum[t].second >= c) {
			nearNum.erase(nearNum.begin() + t);
			t--;
		}
	}

	return nearNum;
}

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	
	int r, c;
	cin >> r >> c;

	vector< vector<char>> map(r);
	vector< pair<int, int>> nearNum;
	bool blocked = false;
	for (int i = 0; i < r; i++) {
		map[i].assign(c, NULL);
	}

	for (int i = 0; i < r; i++) { // X : 빌딩 // 길 : .
		for (int j = 0; j < c; j++) {
			cin >> map[i][j];
		}
	}

	for (int i = 0; i < r; i++) { // X : 빌딩 // 길 : .
		for (int j = 0; j < c; j++) {

			if (map[i][j] == '.') {
				nearNum = nearFunc(r, c, i, j);

				if (blockFunc(map, nearNum, i, j, r, c)) {
					blocked = true;
					break;
				}



				nearNum.clear();
				
			}
			else continue;
			
			if (blocked) break;
		}
	}

	if (blocked) cout << "0";
	else cout << "1";

}

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

문제

문제

출처

ICPC

반례 하나만 들어주시면 감사하겠습니다...

legendmic2 5년 전 0

jh05013 5년 전 1

legendmic2 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말