Crosses Puzzles zoj 4018(zju校試合)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5746
テーマ:
N*Mの格子には、各格子に1つの針があり、最初は上下左右の4つの方向のうちの1つを指し、1つの格子点を1回選択すると、その格子の針が時計回りに回転し、次に指さされた格子の針も時計回りに回転し、ずっと連鎖していきます.  6000回を超えないクリックスキームを構築し、すべての針を上にします.
 
 
問題解:$need[x][y]$はこの格子の針が何回回転して上に向くことができるかを表す.
$A[x][y]$は、この格子が何回アクティブに回転したかを表します.
$B[x][y]$は,この格子がエッジ上の格子の影響で何度受動的に回転したかを示す.
では、次のようになります.
$A[x][y]+B[x][y]=4*K[x][y]+need[x][y]$.(式1)
$B[x][y]=sum(K[x'][y']+[(x',y')を上に移動すると(x,y)])$  (式2)
ここで、$(x',y')は、(x,y)に隣接する格子$である.
最初にすべての$K[x][y]=0$を仮定すると、すべての$A[x][y]$B[x][y]$が計算されます.しかし、一部の$A[x][y]$は負の数になります.
いくつかの$K[x][y]$を大きくすることを考えています.$K[x][y]+=1$を、以前の式が成立するようにするには、$A[x][y]+=4$が必要であり、それに隣接するすべての格子(x',y')は$A[x'][y']-=1,B[x'][y']+=1$が必要である.
 
その後、まずローカルで混乱し始めます.
6000ステップを超えないため、平均格子当たり60ステップです.
従って、上から下へ左から右へ、現在の格子の$A[x][y]<=56$が発見されると、現在の格子+4と、その隣接する格子-1とが絶えず譲られる.
一度やってみると、一番外側の1周目の$A[x][y]$は数十です.真ん中には負の数があります.
上記の過程を繰り返すと、1回やるたびにAが数十の輪に縮小してしまうことに気づきます.10回繰り返すとokになります.
 
思考:どうしてすべて$A[x][y]>=0$にすればいいのでしょうか.
合法的な$A[x][y]$のセットのため、すべての$B[x][y]$と$K[x][y]$を解くことができ、解は唯一である.
証明:式1中のBをKで表すと式2に持ち込まれ、$N^2$個の$K$に関する方程式が得られ、$K$には$N^2$個の変数があるので、解があれば必ず唯一である.
 
 
 
 

 1 #include 
 2 using namespace std;
 3 
 4 #define MAXN 15
 5 
 6 int n, m;
 7 int a[MAXN][MAXN], x[MAXN][MAXN], y[MAXN][MAXN];
 8 int dx[] = {-1, 0, 1, 0};
 9 int dy[] = {0, 1, 0, -1};
10 int ok[4][4], need[MAXN][MAXN];
11 
12 bool check(int x, int y)
13 {
14     return x >= 1 && x <= n && y <= m && y >= 1 && a[x][y] != -1;
15 }
16 
17 int main()
18 {
19     //freopen("in.txt", "r", stdin);
20     ok[0][1] = 1;
21     ok[1][1] = ok[1][2] = 1;
22     ok[2][1] = ok[2][2] = ok[2][3] = 1;
23     
24     int T;
25     scanf("%d", &T);
26     while (T--)
27     {
28         scanf("%d %d", &n, &m);
29         for (int i = 1; i <= n; ++i)
30         {
31             for (int j = 1; j <= m; ++j)
32             {
33                 scanf("%d", &a[i][j]);
34                 if (a[i][j] == -1) continue;
35                 a[i][j] = (4 - a[i][j]) % 4;
36                 need[i][j] = (4 - a[i][j]) % 4;
37             }
38         }
39         memset(x, 0, sizeof(x));
40         memset(y, 0, sizeof(y));
41         int _i, _j;
42         for (int i = 1; i <= n; ++i)
43         {
44             for (int j = 1; j <= m; ++j)
45             {
46                 if (a[i][j] == -1) continue; 
47                 for (int d = 0; d < 4; ++d)
48                 {
49                     _i = i + dx[d], _j = j + dy[d];
50                     if (check(_i, _j) && ok[d][a[_i][_j]])
51                         ++y[i][j];
52                 }
53                 x[i][j] = need[i][j] - y[i][j];
54             }
55         }
56         int iters = 10;
57         while (iters--)
58         {
59             for (int i = 1; i <= n; ++i)
60             {
61                 for (int j = 1; j <= m; ++j)
62                 {
63                     if (a[i][j] == -1) continue;
64                     while (x[i][j] + 4 <= 60)
65                     {
66                         x[i][j] += 4;
67                         for (int d = 0; d < 4; ++d)
68                         {
69                             _i = i + dx[d], _j = j + dy[d];
70                             if (check(_i, _j)) --x[_i][_j], ++y[_i][_j];
71                         }
72                     }
73                 }
74             }
75         }
76         vectorint, int> > ans;
77         for (int i = 1; i <= n; ++i)
78         {
79             for (int j = 1; j <= m; ++j)
80             {
81                 if (a[i][j] == -1) continue;
82                 assert(x[i][j] >= 0);
83                 while (x[i][j] > 0) --x[i][j], ans.push_back(make_pair(i, j));
84             }
85         }
86         printf("%d
", ans.size());
87         for (int i = 0; i < (int)ans.size(); ++i)
88             printf("%d %d
", ans[i].first, ans[i].second);
89     }
90     
91     return 0;
92 }

 
転載先:https://www.cnblogs.com/vb4896/p/8820356.html