---
# System prepended metadata

title: L型磚鑲嵌
tags: [week 10]

---

# L型磚鑲嵌
###### tags: `week 10`
```python=
floor = []
l ,m = map(int ,input().split())

def rotate(gap ,n):              # 大磁磚分割成小磁磚時磁磚樣式會改變
    gap += n
    if gap > 4:gap -=4
    return gap

def center(gap ,l ,x ,y):        # 磁磚樣式跟中心位置的換算
    if gap == 1:return (x - l//4 ,y - l//4)
    if gap == 2:return (x + l//4 ,y - l//4)
    if gap == 3:return (x + l//4 ,y + l//4)
    if gap == 4:return (x - l//4 ,y + l//4)

def collage(gap ,l ,m ,coordinate):    # (磁磚樣式 ,磁磚邊長 ,缺口大小 ,磁磚中心座標)
    global floor
    (x, y) = coordinate
    if l==2:floor.append((gap ,x ,y)) ;return                       # 如果已經是最小的磁磚就不能再分割
    if 1//2 != m:collage(gap ,l//2 ,m ,(x + l//4 ,y + l//4))        # 拼更小塊的
    collage(gap               ,l//2 ,l//2 ,(x ,y))                  # 拼同一個方向、但邊長減半、中心在原地
    collage(gap               ,l//2 ,l//2 ,center(gap ,l ,x ,y))    # 拼同方向、邊長減半、中心改變的
    collage(t:=rotate(gap ,3) ,l//2 ,l//2 ,center(t ,l ,x ,y))      # 拼旋轉三格的
    collage(t:=rotate(gap ,1) ,l//2 ,l//2 ,center(t ,l ,x ,y))      # 旋轉一格
# 從最大塊的開始拼，如果缺口大小不是最大塊邊長的一半就代表還有更小塊的

collage(1 ,l ,m ,(l//2 ,l//2))
floor = sorted(floor, key = lambda x:(x[1], x[2]))    # 把磁磚依照列、行的順序排列，完全不必要的一步
for u in floor:
    for i in u:print(i, end=' ')
    print('')
```

## Solution 2:
> [name=Jason Lin]
### Main Idea:
- 先拆成1個或2個Ｌ型組合，再分別遞迴求解
- tips: 
	- 右下角和左上角的Ｌ型互相對稱，只需要求出一個的座標，再x, y對調即可（當然形狀要用if語句對應）
	- 左下角和中間的L型只是做了平移而已（x, y都平移m/2單位）

#### Case 1:

拆成四個全等的L型：
```
* * * * o o o o         * * * * o o o o
* * * * o o o o         * * * * o o o o
* * * * o o o o    \    * * # # o o o o
* * * * o o o o   --\   * * # # o o o o
* * * * * * * *   --/   @ @ # # # # * *
* * * * * * * *    /    @ @ # # # # * *
* * * * * * * *         @ @ @ @ * * * *
* * * * * * * *         @ @ @ @ * * * *
```
#### Case 2:
```
* * * * x x o o         * * * * o o o o
* * * * x x o o         * * * * o o o o
* * * * x x x x    \    * * # # o o o o         x x
* * * * x x x x   --\   * * # # o o o o   _|_   x x
* * * * * * * *   --/   @ @ # # # # * *    |    x x x x
* * * * * * * *    /    @ @ # # # # * *         x x x x
* * * * * * * *         @ @ @ @ * * * *
* * * * * * * *         @ @ @ @ * * * *
```

### Code:
（用 // 只是為了確保型態為int，而非float）
```python=
def solve(ll,mm):
    if ll==4 and mm==2:   #如果是最小單位L型
        return [[1,1,1],[1,2,2],[2,3,1],[4,1,3]]
    
    sol = []
    if mm==ll/2:   #Case 1
        subtile = solve(ll//2,mm//2)
        subtile_horizontal_rotate = []
        #左下L型左右翻轉為右下L型
        for i in subtile:
            ii = []
            if i[0]==1:ii.append(2)
            elif i[0]==2: ii.append(1)
            elif i[0]==3: ii.append(4)
            elif i[0]==4: ii.append(3)
            ii.extend([mm-i[1],i[2]])
            subtile_horizontal_rotate.append(ii)
        
        sol.extend(subtile)   #加入左下L型
    	
        #加入中間L型    
        for i in subtile:
            sol.append([i[0],i[1]+mm//2,i[2]+mm//2])
        #加入右下與左上L型
        for i in subtile_horizontal_rotate:
            sol.append([i[0],i[1]+mm,i[2]])
            i0=i[0]
            if i0==2: i0=4
            elif i0==4: i0=2
            sol.append([i0,i[2],i[1]+mm])
    
    else:   #Case 2
        sol.extend(solve(ll,ll//2))
        sol.extend(solve(ll//2-mm,mm))
    return sol    

l,m = list(map(int,input().split()))
tiles = solve(l,m)
for i in tiles: print(*i)
```