TIOJ-2145

發表於 更新於 Disqus：

將毯子分成九個格子，中間那格塗黑，再往其他八格遞迴。
給定$N$，輸出邊長為$3^n$經過上述操作所得出的成品。

$N\le 7$

$3^7=2187$，所以可以直接照題述來遞迴，一次打九行程式碼太累了，所以我就將切點存起來，就能用迴圈了。

複雜度的部分，遞迴感覺很難估計，其實可以發現每格只會被處理一次，所以複雜度會是$\mathcal{O}((3^7)^2)$。

嚴謹一點也可由Master Theorem得知。

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
/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#include <bits/stdc++.h>
using namespace std;

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
/*-----------------------------------------------------------------------------------------------------*/

bool owo[2500][2500];

void solve(int lx, int rx, int ly, int ry, bool stat) {
	if(stat) {
		for(int i = lx; i < rx; i++)
			for(int j = ly; j < ry; j++)
				owo[i][j] = 1;
		return;
	}
	if(lx == rx-1)
		return;
	int a[4] = {lx, lx+(rx-lx)/3, rx-(rx-lx)/3, rx};
	int b[4] = {ly, ly+(ry-ly)/3, ry-(ry-ly)/3, ry};
	for(int i = 0; i < 3; i++)
		for(int j = 0; j < 3; j++)
			solve(a[i], a[i+1], b[j], b[j+1], (i==1)&&(j==1));
}

signed main() {
	EmiliaMyWife
	
	int n;
	cin >> n;
	int w = pow(3, n);
	solve(0, w, 0, w, 0);
	for(int i = 0; i < w; i++)
		for(int j = 0; j < w; j++) {
			cout << (owo[i][j]?'#':'.');
			if(j==w-1)
				cout << '\n';
		}

	return 0;
}