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

算法學社
記錄難忘的征途
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>
            亚洲国产成人高清精品| 久久久久国产精品一区三寸| 羞羞漫画18久久大片| 在线中文字幕不卡| 亚洲一区综合| 久久精品国产第一区二区三区最新章节| 亚洲一区视频在线观看视频| 欧美一区二区三区在线| 久久久夜精品| 亚洲国产精品精华液网站| 亚洲欧洲三级| 亚洲自拍偷拍视频| 久久五月激情| 国产精品久久久久aaaa樱花 | 在线性视频日韩欧美| 亚洲无线视频| 久久免费偷拍视频| 欧美三区视频| 怡红院精品视频| 亚洲午夜激情免费视频| 久久久久久亚洲精品不卡4k岛国| 欧美成人免费在线观看| 一区二区三区欧美| 久久人人看视频| 国产精品国产| 亚洲毛片播放| 久久午夜视频| 亚洲免费网站| 欧美日韩精品一区二区在线播放| 国产欧美一区二区精品秋霞影院| 亚洲人体大胆视频| 久久精品国产精品 | 亚洲免费观看在线观看| 午夜精品久久99蜜桃的功能介绍| 欧美a一区二区| 亚洲在线免费观看| 欧美日韩免费高清| 在线精品视频在线观看高清 | 国产综合一区二区| 99re热这里只有精品免费视频| 新狼窝色av性久久久久久| 亚洲大胆av| 欧美在线观看一区| 国产精品视频一二| 在线中文字幕一区| 亚洲日本视频| 欧美成在线观看| 在线观看视频免费一区二区三区| 亚洲免费影视| 99国产精品视频免费观看一公开| 欧美顶级少妇做爰| 亚洲高清久久网| 久久日韩粉嫩一区二区三区| 亚洲欧美在线另类| 国产精品一区一区三区| 亚洲伊人一本大道中文字幕| 亚洲精品乱码久久久久久久久 | 免费不卡中文字幕视频| 香蕉久久夜色| 国产婷婷精品| 久久久久免费视频| 久久久精品国产免费观看同学| 国产日韩在线视频| 久久久久久久久蜜桃| 欧美一区二区在线免费观看| 国产亚洲欧美另类一区二区三区| 午夜精品理论片| 亚洲专区一区| 精品999日本| 欧美国产精品v| 欧美成人精品在线| 在线午夜精品| 亚洲免费小视频| 在线不卡中文字幕| 亚洲国产日韩欧美在线99| 欧美另类视频| 性色av一区二区三区红粉影视| 欧美一区成人| 亚洲激情一区二区| av成人免费在线| 国产日韩欧美不卡| 欧美成人精品在线| 欧美日韩国产一区| 久久av一区二区三区漫画| 久久精品日产第一区二区| 亚洲三级免费观看| 亚洲免费在线视频| 亚洲国产一二三| 亚洲午夜免费福利视频| 尤物九九久久国产精品的特点| 亚洲三级影院| 国产中文一区| 一区二区三区国产在线| 国产亚洲欧美日韩美女| 亚洲第一主播视频| 在线亚洲电影| 性欧美8khd高清极品| 午夜亚洲激情| 亚洲国产日韩美| 亚洲视频一区二区| 亚洲国产精品尤物yw在线观看| 亚洲精品少妇30p| 国内视频一区| 中文精品视频| 亚洲精品国产无天堂网2021| 亚洲资源av| 99视频精品在线| 久久精品导航| 欧美一区二区观看视频| 欧美激情免费在线| 久久一区二区三区av| 国产精品毛片va一区二区三区| 亚洲福利国产精品| 国语自产精品视频在线看8查询8 | 亚洲欧美在线免费| 男女激情视频一区| 久久久国产精品一区二区三区| 欧美日韩国产综合视频在线观看| 美女免费视频一区| 国产午夜精品麻豆| 中文一区二区| 亚洲午夜一区| 欧美日韩三级电影在线| 欧美激情影院| 亚洲国产成人av| 久久精品国产免费看久久精品| 先锋影音久久| 国产精品视频免费在线观看| 一区二区三区欧美在线| 一区二区三区国产在线| 欧美高清视频在线播放| 欧美高清在线视频| 亚洲国产精品va在线看黑人| 久久久噜噜噜久久狠狠50岁| 久久精品国产精品| 国产亚洲亚洲| 久久精品视频免费| 久久亚洲综合网| 在线欧美一区| 欧美刺激午夜性久久久久久久| 欧美激情一区二区三区全黄| 亚洲福利视频一区二区| 免费不卡欧美自拍视频| 亚洲国产另类 国产精品国产免费| 91久久中文字幕| 欧美日韩不卡一区| 亚洲视频精选在线| 久久av一区二区三区漫画| 国产在线精品一区二区夜色| 久久精品日韩欧美| 亚洲国产福利在线| 在线视频一区二区| 国产精品一区二区三区久久| 欧美亚洲日本国产| 蜜臀av性久久久久蜜臀aⅴ| 亚洲国产欧美一区二区三区久久 | 日韩一二在线观看| 欧美日本不卡视频| 日韩视频在线一区二区| 亚洲影院免费| 国产在线视频欧美| 欧美不卡在线| 亚洲在线一区二区三区| 久久人体大胆视频| 99精品国产在热久久婷婷| 国产精品拍天天在线| 久久亚洲精品一区二区| 一本大道久久a久久精品综合| 欧美中文在线观看国产| 亚洲成人在线| 国产精品免费看| 男女激情久久| 亚洲欧美在线一区| 亚洲精品中文字幕有码专区| 久久久久9999亚洲精品| 一区二区三区产品免费精品久久75| 国产欧美精品va在线观看| 欧美大片专区| 久久av在线| 亚洲午夜一区二区三区| 亚洲高清资源综合久久精品| 欧美一区二区在线| 99在线热播精品免费99热| 韩日精品视频一区| 国产精品国产三级国产aⅴ9色| 久久资源在线| 欧美在线观看视频一区二区三区| 亚洲精品久久久久久下一站 | 国产精品美女久久久久久2018 | 国产视频在线观看一区二区三区| 欧美高清不卡在线| 久久精品首页| 亚洲主播在线观看| 亚洲精品欧洲精品| 美女视频一区免费观看| 欧美亚洲一级| 午夜精品视频在线| 亚洲天堂久久| 一区二区激情视频| 亚洲精品视频一区|