사천성 문제를 풀다가 오답이 자꾸 나와서 질문 올립니다.
제가 한 방법은 재귀함수를 써서 모든 좌표에서 상하좌우로 이동하면서 전체 판을 탐색하는 방식입니다.
종료조건은 다음과 같은데요.
탐색을 시작한 판의 문자가 '.'(공백)일경우
4번 이상 꺾은 경우
판을 벗어난 경우 (row, col)
'.'를 제외한 문자를 만난경우
4-1. 시작 문자와 동일한 경우 벡터에 서로의 좌표를 넣고 탐색 종료
4-2. 시작 문자와 다르거나 이미 탐색한(confirm함수) 좌표인경우 종료
drift는 이전과 이동한 방향이 같은 경우는 증가하지않고 다른 경우는 증가합니다.
confirm은 이미 찾은 좌표들이 벡터에 들어가있어서 탐색이 될 때마다 중복인지 검사하는 함수고요.
생각한 대로 짠 코드는 이렇게 되있습니다. 제 생각에는 모든 판을 다 탐색하기 때문에 시관초과가 나올수는 있어도 오답은 안 나올거라고 생각했는데 오답이 나옵니다. 어디서 잘못된건지 찾지를 못해서 질문을 올립니다.
#include<iostream>#include<vector>#include<utility>#include<math.h>usingnamespacestd;boolConfirm(introw,intcol);typedefstructcoordinate{intx;inty;}Coord;classBoard{private:introw;intcol;public:char**board;voidinit_Board();voiddelete_Board();intsearch(charstart,introw,intcol,intdrift,Coordbefore);intGetRow(){returnthis->row;}intGetCol(){returnthis->col;}};typedefstructCordCheck{introw;intcol;}Ck;Coordcord[5]={{-1,0},{1,0},{0,-1},{0,1},{0,0}};CkFstart;pair<Ck,Ck>p;vector<pair<Ck,Ck>>v;voidBoard::init_Board(){inti,j;cin>>this->row>>this->col;this->board=newchar*[row];for(i=0;i<this->row;++i){this->board[i]=newchar[col];}for(i=0;i<this->row;++i){for(j=0;j<this->col;++j){cin>>this->board[i][j];}}}voidBoard::delete_Board(){for(inti=0;i<this->row;++i){delete[]this->board[i];}delete[]this->board;this->board=NULL;this->row=0;this->col=0;}intBoard::search(charstart,introw,intcol,intdrift,Coordbefore){inti,flag=0;/*가능한 경우인지 확인하는 부분 시작*/if(start=='.')return0;//.인 경우 시작조차 안하도록 조치if(drift>3)return0;//4번 이상 꺾은경우 종료if(row<0||row>=this->row)return0;//판 벗어나면 종료if(col<0||col>=this->col)return0;//판 벗어나면 종료if(this->board[row][col]=='.'){;}else{if(this->board[row][col]==start){//똑같은 문양 찾은 경우if(row!=Fstart.row||col!=Fstart.col){//자기자신을 찾는 경우 제외 -> 이때 종료해버리면 시작할때 끝나버려서 그냥 계속 진행if(Confirm(row,col))return0;//중복 검사Cktemp={row,col};p=make_pair(Fstart,temp);v.push_back(p);return1;}}else{return0;}//다른 문양을 만난 경우 종료 -> 장애물 부딪힘}/*가능한 경우인지 확인하는 부분 끝 -> promising*///this->board[row][col] = '/';intx,y;for(i=0;i<4;++i){x=before.x-cord[i].x;y=before.y-cord[i].y;if(!x&&!y){//똑같은 방향으로 움직인 경우 저번거랑 이번 움직임을 빼면 둘다 0flag+=search(start,row+cord[i].y,col+cord[i].x,drift,cord[i]);}elseif(abs(x)!=2&&abs(y)!=2){//왔던길로 다시 가는 경우 둘 중 하나의 절대값은 2 flag+=search(start,row+cord[i].y,col+cord[i].x,drift+1,cord[i]);}else{;}}//this->board[row][col] = '.';returnflag;}intmain(void){inttestcase,comb=0;cin>>testcase;Boardb;inti,j;for(intk=0;k<testcase;++k){b.init_Board();for(i=1;i<b.GetRow()-1;++i){Fstart.row=i;for(j=1;j<b.GetCol()-1;++j){Fstart.col=j;comb+=b.search(b.board[i][j],i,j,0,cord[4]);}}cout<<comb<<endl;comb=0;b.delete_Board();v.clear();}return0;}boolConfirm(introw,intcol)//똑같은거 순서 바꿔서 안 나오게 막아주는 함수{//생각해보니 중복탐색도 막아야함. 그것도 막음vector<pair<Ck,Ck>>::iteratoriter;for(iter=v.begin();iter!=v.end();++iter)//순서가 바뀐경우니까 start가 second에 들어있음{if(Fstart.row==(*iter).second.row&&Fstart.col==(*iter).second.col){if(row==(*iter).first.row&&(*iter).first.col){returntrue;}}if(Fstart.row==(*iter).first.row&&Fstart.col==(*iter).first.col)//중복탐색인 경우 버림 -> 이걸 근본적으로 차단해야되는데 방법이 안 떠올라{if(row==(*iter).second.row&&(*iter).second.col){returntrue;}}}returnfalse;}
7년 전
0개의 댓글이 있습니다.
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면
온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야
합니다. 현재 문제를 푸셨습니다.
yhb0730
사천성 문제를 풀다가 오답이 자꾸 나와서 질문 올립니다.
제가 한 방법은 재귀함수를 써서 모든 좌표에서 상하좌우로 이동하면서 전체 판을 탐색하는 방식입니다.
종료조건은 다음과 같은데요.
'.'를 제외한 문자를 만난경우
4-1. 시작 문자와 동일한 경우 벡터에 서로의 좌표를 넣고 탐색 종료
4-2. 시작 문자와 다르거나 이미 탐색한(confirm함수) 좌표인경우 종료
drift는 이전과 이동한 방향이 같은 경우는 증가하지않고 다른 경우는 증가합니다.
confirm은 이미 찾은 좌표들이 벡터에 들어가있어서 탐색이 될 때마다 중복인지 검사하는 함수고요.
생각한 대로 짠 코드는 이렇게 되있습니다. 제 생각에는 모든 판을 다 탐색하기 때문에 시관초과가 나올수는 있어도 오답은 안 나올거라고 생각했는데 오답이 나옵니다. 어디서 잘못된건지 찾지를 못해서 질문을 올립니다.
7년 전