한번 제 나름대로 코드를 짜봤는데 제 생각이 틀려 오답이 나온것 같아서 다른 분들의 의견을 여쭙고자 합니다.. ㅠㅠ
twoBlock, threeBlock -> 현재 칸을 포함했다는 전제하에 2칸 3칸 블럭을 놓을수 있는 위치들을 저장
status -> 이진수로 25칸 배열의 상태를 나타내어 전달함.
전체적인 알고리즘 설명:
int game(state):
1. state를 토대로 판을 재구성
2. 판에서 새로 놓을수 없다면 패배
3. 새로 놓을 수 있다면, 가능한 모든 곳들을 두어보며 성공할 수 있는 신의 한수가 있다면 즉시 성공을 리턴
4. 신의한수가 한번도 없었다면 패배를 리턴
#include<iostream>usingnamespacestd;charcache[1<<25];boolboard[5][5];inttwoBlock[2][2]={{0,1},{1,0}};//현재칸 포함, 아래칸도 비었거나, 옆에칸도 비었거나intthreeBlock[3][2][2]={{{0,1},{1,0}},{{1,0},{1,1}},{{0,1},{1,1}}};//현재칸 포함해서 가능한 ㄱ, ㄴ모양들boolinsideBoard(intx,inty){//경계 밖을 나갔는지 확인if(x>=0&&x<5&&y>=0&&y<5)returntrue;returnfalse;}boolisLose(){for(inti=0;i<5;i++){for(intj=0;j<5;j++){if(!board[i][j]){//판 처음부터 끝까지 2칸짜리나 3칸짜리 블럭을 놓을수 있는지 확인for(intk=0;k<2;k++){intx=i+twoBlock[k][0];inty=j+twoBlock[k][1];if(insideBoard(x,y)&&!board[x][y])returnfalse;}for(intk=0;k<3;k++){intx1=i+threeBlock[k][0][0];inty1=j+threeBlock[k][0][1];intx2=i+threeBlock[k][1][0];inty2=j+threeBlock[k][1][1];if(insideBoard(x1,y1)&&insideBoard(x2,y2)&&!board[x1][y1]&&!board[x2][y2])returnfalse;}}}}returntrue;}voidmakeBoard(intcurBoard){//현재 정보로 판 구성for(inti=0;i<5;i++){for(intj=0;j<5;j++){intcorrect=1<<(i*5)+j;intflag=correct&curBoard;if(flag)board[i][j]=true;elseboard[i][j]=false;}}}intgame(intcurBoard){makeBoard(curBoard);//그때 그때 판 재구성if(isLose())return-1;//지금 놓을 수 없다면 전사람이 승리char&ret=cache[curBoard];if(ret!=-2)returnret;ret=-1;//내가 승리한 경우가 없다면 패배for(inti=0;i<25;i++){if(((1<<i)&curBoard)==0){//현재 칸이 비어있고intj=i/5;intk=i%5;if(!board[j][k]){for(intl=0;l<2;l++){//두개짜리 블록을 놓을 수 있는 경우에 대해서intx=j+twoBlock[l][0];inty=k+twoBlock[l][1];if(insideBoard(x,y)&&!board[x][y]){intadd=(1<<i)+(1<<((x*5)+y));if(-game(curBoard+add)==1)returnret=1;//한번이라도 승리가 가능하면 승리}}for(intl=0;l<3;l++){//세개짜리 블록을 놓을 수 있는 경우에 대해서intx1=j+threeBlock[l][0][0];inty1=k+threeBlock[l][0][1];intx2=j+threeBlock[l][1][0];inty2=k+threeBlock[l][1][1];if(insideBoard(x1,y1)&&insideBoard(x2,y2)&&!board[x1][y1]&&!board[x2][y2]){intadd=(1<<i)+(1<<((x1*5)+y1))+(1<<((x2*5)+y2));if(-game(curBoard+add)==1)returnret=1;//한번이라도 승리가 가능하면 승리}}}}}returnret;//한번도 못이겼으면 패배}intmain(){inttc;cin>>tc;while(tc--){for(inti=0;i<(1<<25);i++)cache[i]=-2;intstate=0;for(inti=0;i<25;i++){charinput;cin>>input;if(input=='#')state+=(1<<i);}if(game(state)==1)cout<<"WINNING"<<endl;elsecout<<"LOSING"<<endl;}}
pica4500
한번 제 나름대로 코드를 짜봤는데 제 생각이 틀려 오답이 나온것 같아서 다른 분들의 의견을 여쭙고자 합니다.. ㅠㅠ
twoBlock, threeBlock -> 현재 칸을 포함했다는 전제하에 2칸 3칸 블럭을 놓을수 있는 위치들을 저장
status -> 이진수로 25칸 배열의 상태를 나타내어 전달함.
전체적인 알고리즘 설명:
int game(state):
1. state를 토대로 판을 재구성
2. 판에서 새로 놓을수 없다면 패배
3. 새로 놓을 수 있다면, 가능한 모든 곳들을 두어보며 성공할 수 있는 신의 한수가 있다면 즉시 성공을 리턴
4. 신의한수가 한번도 없었다면 패배를 리턴
7년 전