青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

算法學社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0

題目描述:

   在一個15*15的棋盤上下五子棋。3步之內誰能贏。

吐槽:

    因為濫用全局變量,荒廢了一下午...

算法分析:

    
    如果搜3步+判斷局面的話255^4 ,GG
    如果搜2步,判斷制勝點225^3, 時限1s,常數大,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 西月弦 閱讀(322) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            欧美大片在线看免费观看| 亚洲国产裸拍裸体视频在线观看乱了中文 | 久久综合综合久久综合| 中文久久精品| 免费久久99精品国产自在现线| 亚洲黄色精品| 久久精品男女| 亚洲图片自拍偷拍| 一区福利视频| 欧美日韩一区二区在线| 欧美精品三级| 美女国内精品自产拍在线播放| 久久精品国产96久久久香蕉| 一本高清dvd不卡在线观看| 亚洲国产一区二区视频| 亚洲成人资源| 亚洲欧美国产精品va在线观看| 亚洲视频一二区| 亚洲淫片在线视频| 久久久www成人免费毛片麻豆| 蜜臀久久久99精品久久久久久 | 久久精品国产精品亚洲精品| 亚洲欧洲精品一区二区精品久久久| 久久蜜桃香蕉精品一区二区三区| 国产欧美日韩中文字幕在线| 欧美特黄a级高清免费大片a级| 欧美日韩一卡二卡| 亚洲人成网站色ww在线| 亚洲激情视频在线| 久久久久9999亚洲精品| 欧美日韩视频在线第一区| 99在线精品观看| 蜜桃av综合| 永久555www成人免费| 欧美一区二区三区四区在线观看地址 | 国产精品99久久久久久久久久久久| 欧美一区二区三区四区在线观看地址| 欧美日韩国产不卡在线看| 亚洲精品孕妇| 亚洲清纯自拍| 欧美视频在线一区| 小处雏高清一区二区三区| 亚洲欧美在线免费观看| 国产精品揄拍500视频| 久久精品免费观看| 另类欧美日韩国产在线| 日韩午夜在线观看视频| 夜夜狂射影院欧美极品| 国产亚洲欧美aaaa| 免费91麻豆精品国产自产在线观看| 久久蜜桃香蕉精品一区二区三区| 亚洲每日更新| 欧美一区在线视频| 日韩一级在线观看| 小嫩嫩精品导航| 9久re热视频在线精品| 西西人体一区二区| 99在线精品视频在线观看| 亚洲欧美中文日韩在线| 9人人澡人人爽人人精品| 欧美在线影院在线视频| 亚洲一区区二区| 免费成人av在线看| 性伦欧美刺激片在线观看| 欧美xx视频| 欧美激情第3页| 狠狠色噜噜狠狠狠狠色吗综合| 亚洲欧美日本国产有色| 欧美在线影院| 欧美一区二区三区在线视频| 欧美国产一区视频在线观看| 久久久精品日韩| 国产精品wwwwww| 亚洲激情网址| 亚洲成色www久久网站| 一区二区福利| 午夜激情亚洲| 国产综合久久久久久鬼色| 亚洲一区尤物| 久久夜色精品亚洲噜噜国产mv| 国产日韩欧美一区二区三区在线观看 | 亚洲激情欧美| 欧美激情精品久久久| 免费在线视频一区| 欲色影视综合吧| 欧美成人嫩草网站| 日韩视频免费| 久久精品一区二区三区中文字幕 | 亚洲大胆av| 欧美日本国产视频| 亚洲一区二区欧美| 老牛国产精品一区的观看方式| 亚洲国产精品成人| 欧美黄在线观看| 一区二区三区 在线观看视频 | 欧美高清在线精品一区| 亚洲精品中文在线| 久久久国产精品一区| 日韩网站在线看片你懂的| 国产日韩欧美在线播放不卡| 欧美国产一区在线| 香蕉久久夜色精品国产| 亚洲国产一区二区三区青草影视| 欧美中文在线免费| 99国内精品| 亚洲日本在线观看| 亚洲人成人一区二区三区| 黄色亚洲精品| 国产最新精品精品你懂的| 国产精品日韩欧美| 国产精品高清免费在线观看| 欧美精品亚洲| 欧美日韩和欧美的一区二区| 欧美精品999| 欧美午夜精品久久久| 欧美视频你懂的| 国产精品综合av一区二区国产馆| 欧美性色视频在线| 国产精品一区免费观看| 国产三级精品三级| 1024成人| 亚洲一区二区三区在线观看视频| 一区二区久久久久| 欧美一区在线直播| 麻豆精品视频在线观看视频| 女女同性精品视频| 日韩一区二区电影网| 亚洲亚洲精品在线观看 | 欧美与黑人午夜性猛交久久久| 亚洲欧美日韩一区二区三区在线观看 | 久久综合婷婷| 日韩午夜高潮| 久久久另类综合| 欧美黄免费看| 国产视频自拍一区| 夜色激情一区二区| 另类图片综合电影| 亚洲影视在线播放| 欧美日韩在线一区二区| 在线播放国产一区中文字幕剧情欧美 | 午夜亚洲伦理| 欧美激情麻豆| 一区在线免费观看| 欧美一区二区三区视频| 亚洲人成艺术| 欧美激情第三页| 亚洲国产精品传媒在线观看| 欧美一级欧美一级在线播放| 亚洲激情图片小说视频| 久久久女女女女999久久| 国产午夜精品理论片a级探花| 一区二区三区国产在线| 亚洲日本黄色| 欧美日韩精品欧美日韩精品| 99re热这里只有精品视频| 老司机免费视频久久| 久久久欧美精品| 亚洲人www| 9l国产精品久久久久麻豆| 欧美日韩在线观看一区二区三区| 99精品国产一区二区青青牛奶| 欧美国产精品久久| 免费欧美视频| 亚洲私人影吧| 亚洲欧美视频在线观看视频| 国产一区二区看久久| 黑人操亚洲美女惩罚| 免费观看在线综合| 欧美交受高潮1| 久久成人人人人精品欧| 久久尤物视频| 亚洲欧美国产精品专区久久| 久久久噜噜噜久久人人看| 亚洲天堂网在线观看| 欧美综合77777色婷婷| 一本大道久久精品懂色aⅴ| 欧美亚洲三区| 亚洲午夜成aⅴ人片| 久久一区二区三区av| 亚洲欧美日韩综合| 欧美丰满少妇xxxbbb| 久久精品成人| 国产精品成人播放| 亚洲国产欧美一区二区三区久久 | 亚洲精品一区二区三区99| 亚洲一区久久久| 亚洲小视频在线| 欧美99在线视频观看| 免费日韩av| 伊人婷婷欧美激情| 久久青草久久| 欧美黄色视屏| 日韩一级二级三级| 欧美日韩国产在线播放网站| 亚洲国产精品悠悠久久琪琪| 亚洲日本在线观看| 欧美视频在线观看免费| 亚洲图片欧美午夜| 欧美在线视频免费| 国产亚洲成精品久久|