P1074 暴搜代码

本文最后修改于 1005 天前，部分内容可能已经过时！

没错，就是这么暴力

#include <bits/stdc++.h>
int score[9][9]={6,6,6,6,6,6,6,6,6,
             6,7,7,7,7,7,7,7,6,
             6,7,8,8,8,8,8,7,6,
             6,7,8,9,9,9,8,7,6,
             6,7,8,9,10,9,8,7,6,
             6,7,8,9,9,9,8,7,6,
             6,7,8,8,8,8,8,7,6,
             6,7,7,7,7,7,7,7,6,
             6,6,6,6,6,6,6,6,6
             };
int ans;
int sudoku[9][9];
bool check(int number,int hang,int lie)
{int i,j;
    for(i=0;i<9;i++)  //行 
        if(i!=lie&&sudoku[hang][i]==number) return false;
    for(i=0;i<9;i++)  //列 
        if(i!=hang&&sudoku[i][lie]==number) return false;
    for(i=(hang/3)*3;i<=(hang/3)*3+2;i++)  //九宫格 
        for(j=(lie/3)*3;j<=(lie/3)*3+2;j++)
            if(i!=hang&&j!=lie&&sudoku[i][j]==number) return false;   
    return true;
}

void dfs(int step,int sum){
    int x,y;
    if(step<0) {
        if(sum>ans) ans=sum;
        return;
    } 
    x=(step/9);y=(step%9);
    if(sudoku[x][y]>0) 
        dfs(step-1,sum+sudoku[x][y]*score[x][y]);
    else 
        for(int i=1;i<=9;i++)
        if(check(i,x,y)) {
                sudoku[x][y]=i;
                dfs(step-1,sum+sudoku[x][y]*score[x][y]);
                sudoku[x][y]=0;
        }
}
int main(){
    for(int i=0;i<9;i++)
        for(int j=0;j<9;j++)
            scanf("%d",&sudoku[i][j]);
    ans=-1;
    dfs(80,0);
    printf("%d",ans);
}