- Ví dụ : $n$ = 3, $m$ = 3.
```
1 2 3
8 9 4
7 6 5
```
-> Ta thấy có thể xây dựng ma trận từ trái sang phải, rồi từ trên xuống dưới, phải qua trái, xong từ dưới lên trên và lặp lại.
Do đó đầu tiên ta sẽ khởi tạo một mảng để lưu hướng đi :
```cpp
dx[4] = {0, +1, 0, -1};
dy[4] = {+1, 0, -1, 0};
```
- Tiếp theo, ta sẽ khởi tạo một mảng có kích thước $n$ * $m$ và mỗi giá trị đều bằng 0 :
```cpp
a[n + 1][m + 1] = {}
```
- Do mình xét từ chỉ số 1 nên sẽ khai báo là $n + 1$ và $m + 1$, còn lí do vì sao mọi giá trị đều bằng 0 sẽ giải thích ở dưới.
- Sau đó, ta sẽ khởi tạo các biến : $i = 1$, $j = 1$, $cur = 1$, $k = 0$.
- Trong đó :
- $i$ : hàng đang xét.
- $j$ : cột đang xét.
- $cur$ : giá trị của vị trí đang xét.
- $k$ : hướng đi hiện tại (0 : trái sang phải, 1 : trên xuống dưới, 2 : phải qua trái, 3 : dưới lên trên).
- Như đã nói ở trên :
```
có thể xây dựng ma trận từ trái sang phải, rồi từ trên xuống dưới, phải qua trái, xong từ dưới lên trên và lặp lại.
```
- Do đó ta thấy khi đổi hướng ta chỉ cần tăng giá trị cho $k$ và chia lấy dư cho 4 ( vì có 4 hướng đi ).
- Giờ ta sẽ bắt đầu dựng mảng, ta sẽ xây bằng vòng $while$ với điều kiện $cur \leq n * m$. Vì giá trị trong mảng chỉ có thể tới $n$ * $m$.
- Trong vòng lặp :
- Với mỗi gía trị $i$ và $j$ thỏa ($1 \leq i$ && $i \leq n$ && $ 1 \leq j$ && $j \leq m$), ta sẽ gán $a[i][j]$ = $cur$ và tăng $cur$ lên 1 đơn vị. Có thể viết gọn như này :
```cpp
a[i][j] = cur++;
```
- Sau đó ta sẽ tăng $i$ lên $dx[k]$ và $j$ lên $dy[k]$.
- Nếu giá trị $i$ và $j$ không thỏa điều kiện ($1 \leq i$ && $i \leq n$ && $ 1 \leq j$ && $j \leq m$) thì đó là lúc ta phải đổi hướng đi, khi đó ta chỉ cần tăng k lên 1.
```cpp
i -= dx[k]; j -= dy[k]; //Giá trị i, j hiện tại đã không thỏa (nằm ngoài phạm vi của mảng nên ta phải giảm về vị trí cũ).
k = ++k % 4;
i += dx[k]; j += dy[k]; //Vị trỉ i, j đã được gán giá trị nên ta di chuyển.
```
- Vậy là đã xong, tuy nhiên ta nhận thấy rằng việc này sẽ làm vòng lặp vô hạn. Do ta sẽ gán đè lên những giá trị đã xây dựng. Đây là lí do mình khai báo mảng có giá trị bằng 0. Đối với những giá trị chưa xây dựng, ta thấy nó sẽ bằng 0 và ngược lại. Do đó chỉ cần xét thêm nếu ở vị trí $i$, $j$ đã có giá trị thì ta sẽ chuyển hướng :
```cpp
if (!(i >= 1 && i <= n && j >= 1 && j <= m && !a[i][j])){
i -= dx[k]; j -= dy[k]; //Giá trị i, j hiện tại đã không thỏa (nằm ngoài phạm vi của mảng nên ta phải giảm về vị trí cũ).
k = ++k % 4;
i += dx[k]; j += dy[k]; //Vị trỉ i, j đã được gán giá trị nên ta di chuyển.
}
```
- Tổng kết lại :
```cpp
while (cur <= n * m){
a[i][j] = cur++;
i += dx[k]; j += dy[k];
if (!(i >= 1 && i <= n && j >= 1 && j <= m && !a[i][j])){
i -= dx[k]; j -= dy[k];
k = ++k % 4;
i += dx[k]; j += dy[k];
}
}
```
- Ta chỉ cần in ra kết quả là xong. Happy coding!.
toilatu
Created at
2 likes