Hướng dẫn giải của MATRIX07: Ma trận vuông xoắn ốc
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
In ma trận vuông ~n \times n~ có các số tăng dần theo đường xoáy ốc từ ô góc trên trái.
Sub 1: Thu hẹp biên — ~O(n^2)~, dùng khi mọi ~n~
Giữ bốn biên trên, dưới, trái, phải. Mỗi vòng điền hàng trên từ trái sang phải, cột phải từ trên xuống, hàng dưới từ phải sang trái, cột trái từ dưới lên, rồi thu hẹp biên và lặp lại. Mỗi ô được điền đúng một lần.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Bài yêu cầu in ra toàn bộ ma trận, nên độ phức tạp không thể thấp hơn ~n^2~. Không có cách vét cạn nào khác đáng để chia thành sub nên viết một sub duy nhất.
Chương trình đọc ~n~ từ file MATRIX07.INP và in ma trận ra MATRIX07.OUT. Đây là lời giải đầy đủ.
#include <bits/stdc++.h>
using namespace std;
// Dien ma tran theo duong xoay oc: di tu ngoai vao trong bang cach thu hep bien tren/duoi/trai/phai.
// Day la cach nhanh nhat (moi o duoc dien dung mot lan, do phuc tap O(n^2)).
int main() {
freopen("MATRIX07.INP", "r", stdin);
freopen("MATRIX07.OUT", "w", stdout);
int n;
cin >> n;
vector<vector<int>> a(n, vector<int>(n, 0));
int top = 0, bot = n - 1, lef = 0, rig = n - 1;
int v = 1;
while (top <= bot && lef <= rig) {
for (int c = lef; c <= rig; c++) a[top][c] = v++; // hang tren: trai -> phai
top++;
for (int r = top; r <= bot; r++) a[r][rig] = v++; // cot phai: tren -> duoi
rig--;
for (int c = rig; c >= lef && top <= bot; c--) a[bot][c] = v++; // hang duoi: phai -> trai
bot--;
for (int r = bot; r >= top && lef <= rig; r--) a[r][lef] = v++; // cot trai: duoi -> tren
lef++;
}
string out;
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
if (c) out += ' ';
out += to_string(a[r][c]);
}
out += '\n';
}
cout << out;
return 0;
}
Bình luận