大家帮我看看为啥厌氧呀???
#include <bits/stdc++.h>
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int N = 100;
struct node
{ int id, sum;
bool operator<(const node &S)const { sum < S.sum; }
} cou[N];
int f[N][N], s[N][N], idx;
bool leng[N][N], wide[N][N], sq[N][N];
inline void init()
{
memset(leng, true, sizeof(leng));
memset(wide, true, sizeof(wide));
memset(sq, true, sizeof(sq));
for (int i = 1; i <= 9; i ++ ) cou[i].id = i;
}
inline int get(int i, int j)
{
if (i == 5 and j == 5) return 10;
else if (i >= 4 and j >= 4 and i <= 6 and j <= 6) return 9;
else if (i >= 3 and i <= 7 and j >= 3 and j <= 7) return 8;
else if (i >= 2 and i <= 8 and j >= 2 and j <= 8) return 7;
else return 6;
return -1;
}
inline int P(int i,int j)
{
if (i <= 3)
{ if (j <= 3) return 1;
else if (j <= 6) return 2;
else return 3; }
else if (i <= 6)
{ if (j <= 3) return 4;
else if (j <= 6) return 5;
else return 6; }
else
{ if (j <= 3) return 7;
else if (j <= 6) return 8;
else return 9; }
return -1;
}
int res = EOF;
void DFS(int p, int score)
{
if (p == idx)
{
res = max(res, score); return;
}
for (int i = 1; i <= 9; i ++ )
if (leng[ s[p][0] ][i] and wide[ s[p][1] ][i] and sq[ s[p][3] ][i])
{
leng[ s[p][0] ][i] = false;
wide[ s[p][1] ][i] = false;
sq[ s[p][3] ][i] = false;
DFS(p + 1, score + (s[p][2] * i));
leng[ s[p][0] ][i] = true;
wide[ s[p][1] ][i] = true;
sq[ s[p][3] ][i] = true;
}
}
int sum;
signed main()
{
init();
for (int i = 1; i <= 9; i ++ )
{
for (int j = 1; j <= 9; j ++ )
{
f[i][j] = read();
if (f[i][j] > 0)
{
leng[i][ f[i][j] ] = false;
wide[j][ f[i][j] ] = false;
sq[(i - 1) / 3 * 3 + (j - 1) / 3 + 1][ f[i][j] ] = false;
sum += f[i][j] * get(i, j);
}
else cou[i].sum ++ ;
}
}
sort(cou + 1, cou + 9 + 1);
for (int i = 1; i <= 9; i ++ )
for (int j = 1; j <= 9; j ++ )
if (f[cou[i].id][j] == 0)
s[idx][0] = cou[i].id, // ——
s[idx][1] = j, // |
s[idx][2] = get(cou[i].id, j), // score
s[idx ++ ][3] = P(cou[i].id, j); // position
DFS(0, sum);
cout << res << endl;
return 0;
}
// 核心优化 : 某一行的 0 较少,先确定某一行