개발자 톡
17, 18, 20, 21 번 문제만 오답입니다 ㅠ
- 등록일
- 2024-08-31 01:09:41
- 조회수
- 225
- 작성자
- parknomoon
계속해서 찾아보고 있지만, 혼자 힘으로 찾기 어려워 글을 남깁니다 ㅠ
17, 18, 20, 21번 문제가 계속해서 오답으로 체크되는데, 혹시 아시는 반례 있으시면 부탁드리겠습니다ㅠ
아니면 코드상 문제점이 어디인지 혹시 아실까요?
#include "stdio.h"
#include "iostream"
#include "vector"
#include "queue"
using namespace std;
#define MAX 1000
class cPosition {
public:
int row;
int column;
};
int n, m;
char ch;
char map[MAX][MAX] = { 0, };
int GhostMap[MAX][MAX] = { 0, };
int NamooMap[MAX][MAX] = { 0, };
queue<cPosition> qNamoo;
queue<cPosition> qGhost;
cPosition cDestination;
int dr[] = {0, -1, 0, 1};
int dc[] = {-1, 0, 1, 0};
void GhostMove() {
while (!qGhost.empty()) {
cPosition tempGhost = qGhost.front();
qGhost.pop();
int iR = tempGhost.row;
int iC = tempGhost.column;
for (int i = 0; i < 4; i++) {
int nR = iR + dr[i];
int nC = iC + dc[i];
if (nR < 0 || nC < 0 || nR >= n || nC >= m) {
continue;
}
if (GhostMap[nR][nC] != 0) {
continue;
}
GhostMap[nR][nC] = GhostMap[iR][iC] + 1;
tempGhost.row = nR;
tempGhost.column = nC;
qGhost.push(tempGhost);
}
}
}
void NamooMove() {
while (!qNamoo.empty()) {
cPosition tempNamoo = qNamoo.front();
qNamoo.pop();
int iR = tempNamoo.row;
int iC = tempNamoo.column;
if (map[iR][iC] == 'D'){
cout << "Yes";
return;
}
for (int i = 0; i < 4; i++) {
int nR = iR + dr[i];
int nC = iC + dc[i];
if (nR < 0 or nC < 0 or nR >= n or nC >= m) {
continue;
}
if (map[nR][nC] == '#') {
continue;
}
if (NamooMap[nR][nC] != 0) {
continue;
}
if (GhostMap[nR][nC] <= (NamooMap[iR][iC]+1)) {
continue;
}
NamooMap[nR][nC] = NamooMap[iR][iC] + 1;
tempNamoo.row = nR;
tempNamoo.column = nC;
qNamoo.push(tempNamoo);
}
}
cout << "No";
return;
}
void Solution() {
GhostMove();
NamooMove();
/*if (NamooMap[cDestination.row][cDestination.column] == 0 ) {
cout << "No";
}
else {
cout << "Yes";
}*/
}
void Input() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> ch;
map[i][j] = ch;
if (map[i][j] == 'N') {
cPosition tempNamooPos;
tempNamooPos.row = i;
tempNamooPos.column = j;
qNamoo.push(tempNamooPos);
NamooMap[i][j] = 1;
}
else if (map[i][j] == 'G') {
cPosition tempPos;
tempPos.row = i;
tempPos.column = j;
qGhost.push(tempPos);
GhostMap[i][j] = 1;
}
else if (map[i][j] == 'D') {
cDestination.row = i;
cDestination.column = j;
}
}
}
}
int main(int argc, char** argv)
{
Input();
Solution();
return 0;
}