80分程序求助 有注释
查看原帖
80分程序求助 有注释
213727
WuTUT楼主2020/7/14 15:56

按照题解写的,对所有待填入数字的点按所在行、列、九宫格0的个数进行排序,然后搜索,看到有人说这么搜不会TLE 所以问问我的代码是不是哪里有问题

下面是代码

#include <iostream>
#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;

const int sco[10][10] = { //预处理每个格子分数
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 6, 6, 6, 6, 6, 6, 6, 6, 6},
    {0, 6, 7, 7, 7, 7, 7, 7, 7, 6},
    {0, 6, 7, 8, 8, 8, 8, 8, 7, 6},
    {0, 6, 7, 8, 9, 9, 9, 8, 7, 6},
    {0, 6, 7, 8, 9, 10, 9, 8, 7, 6},
    {0, 6, 7, 8, 9, 9, 9, 8, 7, 6},
    {0, 6, 7, 8, 8, 8, 8, 8, 7, 6},
    {0, 6, 7, 7, 7, 7, 7, 7, 7, 6},
    {0, 6, 6, 6, 6, 6, 6, 6, 6, 6}};
int f[10][10], row[10][10], col[10][10], block[10][10];
//f原图,row第i行第j的个数是否存在,col第i列第j个数是否存在,block第i个九宫格第j个数是否存在
int ans = -1;                     //输出答案
int cnt;                          //一共有多少个0
int cntr[10], cntc[10], cntb[10]; //第i行0的个数,第i列0的个数,第i个九宫格0的个数

struct Node //原图中0的点
{
    int x, y, val; //行位置,列位置,不确定度:所在行的0+所在列的0+所在九宫格的0
    bool operator<(const Node &rhs) const
    {
        return val < rhs.val;
    }
} s[100];                       //为0的点的集合
inline int belong(int x, int y) //找到属于哪个九宫格 编号1~9
{
    int tmp = 0;
    int a = (x - 1) / 3 + 1;
    int b = (y - 1) / 3 + 1;
    return (a - 1) * 3 + b;
}
void cal() //计算此时的得分
{
    int tmp = 0;
    for (int i = 1; i <= 9; i++)
    {
        for (int j = 1; j <= 9; j++)
        {
            tmp += f[i][j] * sco[i][j];
        }
    }
    ans = max(ans, tmp);
}
void dfs(int now) //now表示搜索到了第now个点
{
    int x = s[now].x;
    int y = s[now].y;
    if (now == cnt)
    {
        cal();
    }
    int b = belong(x, y); //在哪一个九宫格
    for (int i = 1; i <= 9; i++)
    {
        //  cout << row[x][i] << col[y][i] << block[b][i] << f[x][y] << endl;
        if (!row[x][i] && !col[y][i] && !block[b][i] && !f[x][y])
        { //第x行是否有数字i   第y列是否有数字i 。。。 原图中是否这个位置还没有填
            f[x][y] = i, row[x][i] = 1, col[y][i] = 1, block[b][i] = 1;
            dfs(now + 1);
            f[x][y] = 0, row[x][i] = 0, col[y][i] = 0, block[b][i] = 0;
        }
    }
}
int main()
{
    freopen("data.in", "r", stdin);
    for (int i = 1; i <= 9; i++)
    {
        for (int j = 1; j <= 9; j++)
        {
            cin >> f[i][j];
            if (f[i][j])
            { //标记第i行这个数字已存在。。。
                row[i][f[i][j]] = 1, col[j][f[i][j]] = 1, block[belong(i, j)][f[i][j]] = 1;
            }
            else
            {
                cntr[i]++, cntc[j]++, cntb[belong(i, j)]++, cnt++; //统计行和列0的个数
                s[cnt - 1].x = i, s[cnt - 1].y = j;                //把0的位置加入点集合s中
            }
        }
    }
    //编号0~cnt-1  计算每一个待填入数字位置的不确定度
    for (int i = 0; i < cnt; i++)
    {
        s[i].val = cntr[s[i].x] + cntc[s[i].y] + cntb[belong(s[i].x, s[i].y)];
    }
    sort(s, s + cnt); //对点按不确定度排序
    // for (int i = 0; i < cnt; i++)
    // {
    //     cout << s[i].x << " " << s[i].y << " " << s[i].val << endl;
    // }
    dfs(0);
    cout << ans << endl;
    return 0;
}

谢谢大佬

2020/7/14 15:56
加载中...