현재 위치에서 갈 수 있는 돌을 canGo vector에 넣고
방문한 돌들은 remainList에서 제거하는 방식으로
길을 찾아가는 알고리즘인데 java에서는 같은 알고리즘으로
정답이 나오는데 C++에선 오답이 나옵니다.
어떤 케이스가 오답이 나오는지 알수 있으면
해결할 수 있을것 같은데 도움 부탁드립니다.
질문 처음 올리는데 지적할 부분있으면 말씀해 주세요.
[[problem:BRAVEDUCK]]
#include<iostream>
#include<list>
#include<string>
#include<vector>
#include<math.h>
using namespace std;
int jump;
int endx;
int endy;
struct vertex{
int x;
int y;
}end;
list<vertex> remainList;
bool haspath;
void findPath(vertex nowLoc){
vector<vertex> canGo;
list<vertex>::iterator pos = remainList.begin();
double x=0;
double y=0;
for(pos; pos!=remainList.end();){
x=pos->x;
y=pos->y;
//temp는 현재위치에서 대상 돌과의 거리
double temp = sqrt(pow((double)nowLoc.x-x,2)+pow((double)nowLoc.y-y,2));
//점프 가능한 거리면 현재위치에서 방문할 수 있는 돌, canGo리스트에 삽입
if(temp<=jump){
//갈수 있는 돌이 목표지점이면 true
if(x==endx&&y==endy){
haspath=true;
return;
}
//현재 위치에서 방문할수 있는 돌입력 후
//두 번 방문 하지 않기 위해 리스트에서 제거
canGo.push_back(*pos);
pos=remainList.erase(pos);
}else{
pos++;
}
}
if(canGo.size()==0){
return;
}
//갈 수 잇는 돌들을 모두 방문해 본다
for(int i=0; i<canGo.size(); i++){
if(haspath==true)
return;
nowLoc = canGo[i];
findPath(nowLoc);
}
}
int main(){
int cases;
cin>>cases;
string *result = new string[cases];
for(int i=0; i<cases; i++){
haspath=false;
//점프 거리 입력
cin>>jump;
//시작점 입력
vertex start;
cin>>start.x;
cin>>start.y;
//끝점 입력
vertex end;
cin>>end.x;
cin>>end.y;
endx=end.x;
endy=end.y;
//돌 개수
int vertexnum;
cin>>vertexnum;
//돌 좌표 입력
for(int j=0; j<vertexnum; j++){
vertex t;
cin>>t.x;
cin>>t.y;
remainList.push_back(t);
}
remainList.push_back(end);
findPath(start);
if(haspath==true){
result[i]="YES";
}else{
result[i]="NO";
}
}//for cases 끝
//결과 출력
for(int i=0; i<cases; i++){
cout<<result[i]<<endl;
}
}//main 끝
naka15
현재 위치에서 갈 수 있는 돌을 canGo vector에 넣고
방문한 돌들은 remainList에서 제거하는 방식으로
길을 찾아가는 알고리즘인데 java에서는 같은 알고리즘으로
정답이 나오는데 C++에선 오답이 나옵니다.
어떤 케이스가 오답이 나오는지 알수 있으면
해결할 수 있을것 같은데 도움 부탁드립니다.
질문 처음 올리는데 지적할 부분있으면 말씀해 주세요.
[[problem:BRAVEDUCK]]
11년 전