Games Code

Luojt95 · 2025-07-09 16:18:19 · 休闲·娱乐

1.数独

(1) code

#include<bits/stdc++.h>
using namespace std;
int a[10][10];
bool h[10][10],l[10][10],g[10][10];
void print(void){
    for(int i=1;i<=9;i++){
        for(int j=1;j<=9;j++)
            cout<<a[i][j]<<' ';
        cout<<'\n';
    }
    exit(0);
}
void dfs(int x,int y){
    if(a[x][y]!=0){
        if(x==9&&y==9) print();
        else if(y!=9) dfs(x,y+1);
        else dfs(x+1,1);
    }
    else{
        for(int i=1;i<=9;i++){
            if(!h[x][i]&&!l[y][i]&&!g[(x-1)/3*3+(y-1)/3+1][i]){
                a[x][y]=i;
                h[x][i]=true;
                l[y][i]=true;
                g[(x-1)/3*3+(y-1)/3+1][i]=true;
                if(x==9&&y==9) print();
                else if(y!=9) dfs(x,y+1);
                else dfs(x+1,1);
                a[x][y]=0;
                h[x][i]=false;
                l[y][i]=false;
                g[(x-1)/3*3+(y-1)/3+1][i]=false;
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    for(int i=1;i<=9;i++){
        for(int j=1;j<=9;j++){
            cin>>a[i][j];
            if(a[i][j]!=0&&(h[i][a[i][j]]||l[j][a[i][j]]||g[(i-1)/3*3+(j-1)/3+1][a[i][j]])){
                cout<<"Input Error!";
                return 0;
            }
            h[i][a[i][j]]=true;
            l[j][a[i][j]]=true;
            g[(i-1)/3*3+(j-1)/3+1][a[i][j]]=true;
        }
    }
    dfs(1,1);
    cout<<"Input Error!";
    return 0;
}

(2) play

自动甄别错误+极快时间填完数独。

(3) time

时间复杂度平均 10ms 。

2.华容道

(1) code

#include<bits/stdc++.h>
const int SFT=1;
using namespace std;
queue<string> q;
map<string,int> dis;
int d[]={-3,-1,1,3};
int main()
{
    string s;
    cin>>s;
    q.push(s);
    dis[s]=1;
    while(!q.empty())
    {
        string p=q.front();
        q.pop();
        if(p=="123456780")
        {
            cout<<dis[p]-SFT;
            return 0;
        }
        int p_pos=p.find("0");
        for(int i=0;i<4;i++)
        {
            int n_pos=p_pos+d[i];
            if((n_pos<0||n_pos>8)||(p_pos==3&&n_pos==2)||(p_pos==5&&n_pos==6)||(p_pos==2&&n_pos==3)||(p_pos==6&&n_pos==5)) continue;
            string n=p;
            swap(n[p_pos],n[n_pos]);
            if(!dis[n])
            {
                q.push(n);
                dis[n]=dis[p]+1;
            }
        }
    }
    cout<<"Input Error!";
    return 0;
}

(2) play

自动甄别错误+极快时间输出最少滑动次数。

(3) time

时间复杂度平均 50ms 。