SGU125 解题手记
　　For each state the number of neighbors, B [i, j], that have a larger army, is known. 这句话应该改成：For each state the number of neighbors that have a larger army, is known as B [i, j].
　　搜索一下应该可以，格子中数字范围是1~9。
　　搜索顺序：n=2时只有4个角，n=3时(1,2)->(2,1)->(2,3)->(3,2)->(2,2)，然后4个角。
　　搜索策略：
　　1.对A[i,j]，从1搜到9；
　　2.前4个格子随意枚举；
　　3.第5个格子和4个角要使自身满足条件：周围比A［i,j]大的格子数<=B[i,j]且比A［i,j]大的格子数+没搜过的格子数>=B[i,j]；
　　4.第5个格子和4个角还要探察旁边的格子。

　　Submit 1: WA on 2。check里面的"(x-1)%n?"应该是"x%n?"。
　　Submit 2: AC。

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

#include <iostream>
using namespace std;
 
const int squeue[2][9][6]={{{2,1,2,0,0,0},
                            {2,0,3,0,0,1},
                            {2,0,3,0,0,2},
                            {2,1,2,0,0,3}},
                           {{3,0,2,4,0,1},
                            {3,0,6,4,0,3},
                            {3,2,8,4,0,5},
                            {3,6,8,4,0,7},
                            {4,1,3,5,7,4},
                            {2,1,3,0,0,0},
                            {2,1,5,0,0,2},
                            {2,3,7,0,0,6},
                            {2,5,7,0,0,8}}};
 
int mA[9],mB[9];
int n,nk;
 
bool check(int x)
{
    if (!mA[x]) return true;
    int c1(0),c2(0);
    x>=n?mA[x-n]?mA[x-n]>mA[x]?++c1:0:++c2:0;
    (x+1)%n?mA[x+1]?mA[x+1]>mA[x]?++c1:0:++c2:0;
    x<n*(n-1)?mA[x+n]?mA[x+n]>mA[x]?++c1:0:++c2:0;
    x%n?mA[x-1]?mA[x-1]>mA[x]?++c1:0:++c2:0;
    return c1<=mB[x] && c1+c2>=mB[x];
}
 
bool find(int p)
{
    bool passed=false,checkr=true;
    for (int i=1;i<=9;++i)
    {
        mA[squeue[nk][p][5]]=i;
        if ((n==3 && p<4) || (checkr=check(squeue[nk][p][5])))
        {
            bool pass=passed=true;
            for (int j=1;j<=squeue[nk][p][0];++j)
                if (!(pass&=check(squeue[nk][p][j]))) break;
            if (pass && (p==n*n-1 || find(p+1))) return true;
        }
        mA[squeue[nk][p][5]]=0;
        if (passed && !checkr) break;
    }
    return false;
}
 
int main()
{
    scanf("%d",&n); nk=n-2;
    for (int i=0;i<n*n;++i) scanf("%d",&mB[i]);
    if (n==1)
        if (!mB[0]) printf("1\n");
        else printf("NO SOLUTION\n");
    else
        if (find(0))
            for (int i=0;i<n*n;++i)
                if ((i+1)%n==0) printf("%d\n",mA[i]);
                else printf("%d ",mA[i]);
        else printf("NO SOLUTION\n");
    return 0;
}