锐客网

  1. 首页 > it技术 > >

wiki-1004-四子连棋

【wiki-1004-四子连棋】恶心！！！写了好久，调了好久，恶心！！！从中领悟了一个道理“复制有风险，粘贴需谨慎。”（因为程序中有类似的部分，所以就复制粘贴，结果忘记改变量名了，找了好久......555555555555555555555555555）



#include #include #include #include #include #include #include #include using namespace std; struct aaa { int x,y; }; struct node { int hash[5][5],step,flag; aaa kb1,kb2; }; queue q; maphh; node start; void init() { freopen("wiki.in","r",stdin); freopen("wiki.out","w",stdout); }string gethash(node st) { string qwer = ""; for(int i=1; i<=4; i++) { for(int j=1; j<=4; j++) { qwer =qwer + (char)(st.hash[i][j]+'0'); } } return qwer; }bool trytoinsert(node st) { string qqq=gethash(st); if(hh[qqq]) return false; hh[qqq]=1; return true; }void check(node st) { if((st.hash[1][1] == st.hash[2][2] && st.hash[3][3] == st.hash[4][4] && st.hash[2][2] == st.hash[3][3]) || (st.hash[1][4] == st.hash[2][3] && st.hash[2][3] == st.hash[3][2] && st.hash[3][2] == st.hash[4][1])) {printf("%d",st.step); exit(0); } if((st.hash[1][1] == st.hash[1][2] && st.hash[1][2] == st.hash[1][3] && st.hash[1][3] == st.hash[1][4]) || (st.hash[2][1] == st.hash[2][2] && st.hash[2][2] == st.hash[2][3] && st.hash[2][3] == st.hash[2][4])) {printf("%d",st.step); exit(0); } if((st.hash[3][1] == st.hash[3][2] && st.hash[3][2] == st.hash[3][3] && st.hash[3][3] == st.hash[3][4]) || (st.hash[4][1] == st.hash[4][2] && st.hash[4][2] == st.hash[4][3] && st.hash[4][3] == st.hash[4][4])) {printf("%d",st.step); exit(0); } if((st.hash[1][1] == st.hash[2][1] && st.hash[2][1] == st.hash[3][1] && st.hash[3][1] == st.hash[4][1]) || (st.hash[1][2] == st.hash[2][2] && st.hash[2][2] == st.hash[3][2] && st.hash[3][2] == st.hash[4][2])) {printf("%d",st.step); exit(0); } if((st.hash[1][3] == st.hash[2][3] && st.hash[2][3] == st.hash[3][3] && st.hash[3][3] == st.hash[4][3]) || (st.hash[1][4] == st.hash[2][4] && st.hash[2][4] == st.hash[3][4] && st.hash[3][4] == st.hash[4][4])) {printf("%d",st.step); exit(0); } }void readdata() { char qq[10][10]; int cnt=0; for(int i=0; i<4; i++) { scanf("%s",qq[i]); for(int j=0; j<4; j++) { if(qq[i][j]=='B') start.hash[i+1][j+1]=1; if(qq[i][j]=='W') start.hash[i+1][j+1]=2; if(qq[i][j]=='O') { start.hash[i+1][j+1]=0; if(!cnt) { start.kb1.x=i+1; start.kb1.y=j+1; cnt++; } else { start.kb2.x=i+1; start.kb2.y=j+1; } } } } start.flag=1; start.step=0; check(start); if(trytoinsert(start)) q.push(start); start.flag=2; q.push(start); }int dx[]={1,-1,0,0}; int dy[]={0,0,1,-1}; void work() { while(!q.empty()) { node cur=q.front(); q.pop(); for(int i=0; i<4; i++) { node st,sd; memcpy(&st,&cur,sizeof(cur)); memcpy(&sd,&cur,sizeof(cur)); int x1=st.kb1.x,y1=st.kb1.y,x2=st.kb2.x,y2=st.kb2.y; int newx1=x1+dx[i],newy1=y1+dy[i]; while(newx1 > 0 && newx1 < 5 && newy1 > 0 && newy1 < 5 && st.hash[newx1][newy1]!=0) { if((st.hash[newx1][newy1]==1 && st.flag==1) || (st.hash[newx1][newy1]==2 && st.flag==2)) break; if(st.hash[newx1][newy1]==1) st.flag=1; else st.flag=2; st.hash[x1][y1] = st.hash[newx1][newy1]; st.hash[newx1][newy1]=0; st.kb1.x=newx1,st.kb1.y=newy1; st.step++; check(st); if(trytoinsert(st)) q.push(st); break; } int newx2=x2+dx[i],newy2=y2+dy[i]; while(newx2 > 0 && newx2 < 5 && newy2 > 0 && newy2 < 5 && sd.hash[newx2][newy2]!=0) { if((sd.hash[newx2][newy2]==1 && sd.flag==1) || (sd.hash[newx2][newy2]==2 && sd.flag==2)) break; if(sd.hash[newx2][newy2]==1) sd.flag=1; else sd.flag=2; sd.hash[x2][y2]=sd.hash[newx2][newy2]; sd.hash[newx2][newy2]=0; sd.kb2.x=newx2,sd.kb2.y=newy2; sd.step++; check(sd); if(trytoinsert(sd)) q.push(sd); break; } } } }int main() { init(); readdata(); work(); return 0; }




    推荐阅读


    上一篇：广东工业大学新生赛决赛E题

    下一篇：数学方法|广东工业大学新生赛决赛F题