题解 | 弹珠游戏

#include <iostream>
#include <vector>
#include <string>
#include <map>
std::map<std::vector<std::string>,int> nums;
int hanshu(std::vector<std::string> s){
    if(nums.count(s)){
        return nums[s];
    }
    int shu=0;
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            if(s[i][j]=='.'){
                shu++;
            }
        }
    }
    if(shu==0){
        return nums[s]=-1;
    }
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            if(s[i][j]=='.'){
                std::vector<std::string> now_s=s;
                for(int p=i;p<std::min(4,i+3);p++){
                    if(now_s[p][j]=='.'){
                        now_s[p][j]='*';
                        if(hanshu(now_s)==-1){
                            return nums[s]=1;
                        }
                    }else{
                        break;
                    }
                }
                now_s=s;
                for(int p=j;p<std::min(j+3,4);p++){
                    if(now_s[i][p]=='.'){
                        now_s[i][p]='*';
                        if(hanshu(now_s)==-1){
                            return nums[s]=1;
                        }
                    }else{
                        break;
                    }
                }
                now_s=s;
                for(int p=i,q=j;p<std::min(4,i+3)&&q<std::min(4,j+3);p++,q++){
                    if(now_s[p][q]=='.'){
                        now_s[p][q]='*';
                        if(hanshu(now_s)==-1){
                            return nums[s]=1;
                        }
                    }else{
                        break;
                    }
                }
                now_s=s;
                for(int p=i,q=j;p<std::min(4,i+3)&&q>std::max(-1,j-3);p++,q--){
                    if(now_s[p][q]=='.'){
                        now_s[p][q]='*';
                        if(hanshu(now_s)==-1){
                            return nums[s]=1;
                        }
                    }else{
                        break;
                    }
                }
            }
        }
    }
    return nums[s]=-1;
}
int main(){
    int t;
    std::cin>>t;
    std::vector<std::pair<int,int>> weizhi={{0,0},{1,0},{0,1},{2,0},{1,1},{0,2},{3,0},{2,1},{1,2},{0,3},{3,1},{2,2},{1,3},{3,2},{2,3},{3,3}};
    while(t--){
        std::vector<std::string> s(4,"....");
        for(int i=0;i<16;i++){
            int x=weizhi[i].first;
            int y=weizhi[i].second;
            char p;
            std::cin>>p;
            s[x][y]=p;
        }
        int shu=hanshu(s);
            if(shu==1){
                std::cout<<"Alice"<<std::endl;
            }else{
                std::cout<<"Bob"<<std::endl;
            }
    }
    return 0;
}