• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            算法學(xué)社
            記錄難忘的征途
            posts - 141,comments - 220,trackbacks - 0

            題目描述:

               在一個(gè)15*15的棋盤上下五子棋。3步之內(nèi)誰(shuí)能贏。

            吐槽:

                因?yàn)闉E用全局變量,荒廢了一下午...

            算法分析:

                
                如果搜3步+判斷局面的話255^4 ,GG
                如果搜2步,判斷制勝點(diǎn)225^3, 時(shí)限1s,常數(shù)大,GG
                如果搜1步,判斷后手的行為(直接贏下比賽或者不讓先手贏下比賽) 225^2,AC
            #include<cstdio>
            #include<cstring>
            #include<iostream>
            using namespace std;
            const int N = 15;
            int x,y;
            int dir[8][2] = {
                {1,0} , {-1,0},
                {0,1} , {0,-1},
                {-1,1}, {1,-1},
                {1,1} , {-1,-1}
            };
            inline bool jg(int X,int Y){
                return X>=0 && Y >=0 && X<N && Y<N;
            }
            inline bool chk(int num[N][N],int c) {
                x = y = -1;
                int sx,sy,flag;
                for(int i=0;i<N;i++)
                    for(int j=0;j<N;j++) if(num[i][j] == -1)
                        for(int p =0; p< 8; p+=2)
                            for(int a=0;a<5;a++){
                                int b = 4-a;
                                flag = 0;
                                for(int k=1;k<=a;k++){
                                    sx = i + k * dir[p][0];
                                    sy = j + k * dir[p][1];
                                    if(jg(sx,sy) && num[sx][sy] == c) ; else flag = 1;
                                }
                                for(int k=1;k<=b;k++){
                                    sx = i + k * dir[p+1][0];
                                    sy = j + k * dir[p+1][1];
                                    if(jg(sx,sy) && num[sx][sy] == c) ; else flag = 1;
                                }
                                if(!flag){
                                    x = i; y = j; return 1;
                                }
                            }
                return 0;
            }
            void OP(int num[N][N]){for(int i=0;i<N;i++) {for(int j=0;j<N;j++) if(num[i][j]==-1)cout<<"*";else cout<<num[i][j];cout<<endl;}cout<<endl;}
            int dfs(int lvl, int num[N][N], int c) {
                int s = chk(num,c);
                if(lvl == 2 || s) {
                    return s;
                }
                if(lvl == 1) {
                    if(!chk(num,c^1)) return 0;
                    int tx = x, ty = y;
                    num[x][y] = c;
                    int S = dfs(lvl+1,num,c^1);
                    num[tx][ty] = -1;
                    if(S) return -1;
                    return 0;
                }
                int flag = 1;
                for(int i=0;i<N;i++)
                    for(int j=0;j<N;j++) if(num[i][j] == -1){
                        num[i][j] = c;
                        int s = dfs(lvl+1,num,c^1);
                        num[i][j] = -1;
                        x = i, y = j;
                        if(s == -1) return 1;
                        flag &= s;
                    }
                if(flag == 1) return -1;
                return 0;
            }
            int main(){
                int num[N][N];
                int c,n;
                while(~scanf("%d",&n) ,n) {
                    memset(num,-1,sizeof(num));
                    int suma = 0, sumb = 0, p =-1;
                    for(int i=0;i<n;i++){
                        scanf("%d%d%d",&x,&y,&c);
                        num[x][y] = c;
                        suma += c ==0;
                        sumb += c ==1;
                    }
                    if(suma == sumb) p = 1;
                    if(suma == sumb-1) p = 0;
                    //OP(num);
                    if(p == -1) {
                        puts("Invalid.");
                        continue;
                    }
                    int f = chk(num,p);
                    int s = dfs(0,num,p);
                    if(s == 0) {
                        puts("Cannot win in 3 moves.");
                    }
                    else if(s == 1) {
                        printf("Place %s at (%d,%d) to win in %s.\n",p?"black":"white",x,y,f? "1 move":"3 moves");
                    }
                    else puts("Lose in 2 moves.");
                }
            }
            posted on 2012-07-30 21:31 西月弦 閱讀(312) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 解題報(bào)告
            久久久久久无码Av成人影院| 九九热久久免费视频| 久久精品国产亚洲AV不卡| 色综合久久夜色精品国产| 亚洲精品无码久久久久| 久久er国产精品免费观看2| 久久久精品国产亚洲成人满18免费网站 | 99久久99久久精品国产片| 香蕉aa三级久久毛片| 99久久www免费人成精品| 久久人人超碰精品CAOPOREN| 国产精品久久久久久一区二区三区| 亚洲国产香蕉人人爽成AV片久久 | 久久精品嫩草影院| 精品久久久久久无码不卡| 久久综合久久性久99毛片| 亚洲AV无码久久精品蜜桃| 久久播电影网| 77777亚洲午夜久久多喷| 久久久久国产精品人妻| 国产精品免费久久久久影院| 99久久国产综合精品五月天喷水| 久久精品国产乱子伦| 精品久久久久久亚洲| 亚洲AV日韩精品久久久久久| 欧美日韩精品久久久久| 久久99精品九九九久久婷婷| 99久久er这里只有精品18| 国产精品美女久久久久网| 亚洲欧美成人综合久久久| 久久久久亚洲精品日久生情| 久久久国产精品| 女人高潮久久久叫人喷水| 久久亚洲精品无码播放| 欧美激情精品久久久久久| 久久久中文字幕日本| 日本国产精品久久| 国产精品久久久久久久久软件| 久久久久国产成人精品亚洲午夜| 国产精品欧美亚洲韩国日本久久 | 国产高潮久久免费观看|