현재 위치에서 갈 수 있는 돌을 canGo vector에 넣고
방문한 돌들은 remainList에서 제거하는 방식으로
길을 찾아가는 알고리즘인데 java에서는 같은 알고리즘으로
정답이 나오는데 C++에선 오답이 나옵니다.
어떤 케이스가 오답이 나오는지 알수 있으면
해결할 수 있을것 같은데 도움 부탁드립니다.
질문 처음 올리는데 지적할 부분있으면 말씀해 주세요. BRAVEDUCK
#include<iostream>#include<list>#include<string>#include<vector>#include<math.h>usingnamespacestd;intjump;intendx;intendy;structvertex{intx;inty;}end;list<vertex>remainList;boolhaspath;voidfindPath(vertexnowLoc){vector<vertex>canGo;list<vertex>::iteratorpos=remainList.begin();doublex=0;doubley=0;for(pos;pos!=remainList.end();){x=pos->x;y=pos->y;//temp는 현재위치에서 대상 돌과의 거리doubletemp=sqrt(pow((double)nowLoc.x-x,2)+pow((double)nowLoc.y-y,2));//점프 가능한 거리면 현재위치에서 방문할 수 있는 돌, canGo리스트에 삽입if(temp<=jump){//갈수 있는 돌이 목표지점이면 trueif(x==endx&&y==endy){haspath=true;return;}//현재 위치에서 방문할수 있는 돌입력 후//두 번 방문 하지 않기 위해 리스트에서 제거canGo.push_back(*pos);pos=remainList.erase(pos);}else{pos++;}}if(canGo.size()==0){return;}//갈 수 잇는 돌들을 모두 방문해 본다for(inti=0;i<canGo.size();i++){if(haspath==true)return;nowLoc=canGo[i];findPath(nowLoc);}}intmain(){intcases;cin>>cases;string*result=newstring[cases];for(inti=0;i<cases;i++){haspath=false;//점프 거리 입력cin>>jump;//시작점 입력vertexstart;cin>>start.x;cin>>start.y;//끝점 입력vertexend;cin>>end.x;cin>>end.y;endx=end.x;endy=end.y;//돌 개수intvertexnum;cin>>vertexnum;//돌 좌표 입력for(intj=0;j<vertexnum;j++){vertext;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(inti=0;i<cases;i++){cout<<result[i]<<endl;}}//main 끝
naka15
현재 위치에서 갈 수 있는 돌을 canGo vector에 넣고
방문한 돌들은 remainList에서 제거하는 방식으로
길을 찾아가는 알고리즘인데 java에서는 같은 알고리즘으로
정답이 나오는데 C++에선 오답이 나옵니다.
어떤 케이스가 오답이 나오는지 알수 있으면
해결할 수 있을것 같은데 도움 부탁드립니다.
질문 처음 올리는데 지적할 부분있으면 말씀해 주세요.
BRAVEDUCK
9년 전