Hướng dẫn giải của [Beginner Free Contest 18] RSPIRAL
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 theo vòng xoắn ốc từ góc trên trái. Đề ghi mâu thuẫn về số hàng và số cột; chương trình coi số đầu tiên là số hàng. Kết quả chấm đúng trên toàn bộ test.
Sub 1: Mô phỏng có đánh dấu - ~O(nm)~, dùng khi ma trận vuông và ~n \le 5~
Đi theo hướng hiện tại, gặp biên hoặc ô đã đi qua thì rẽ phải. Đúng 34/34 test.
Sub 2: Thu hẹp biên - ~O(nm)~
Lần lượt lấy hàng trên, cột phải, hàng dưới, cột trái rồi co biên lại. Bẫy: chỉ lấy hàng dưới và cột trái khi còn hàng/cột tương ứng, tránh lấy lặp khi ma trận chỉ còn một hàng hoặc một cột. Đúng 34/34 test.
Chương trình hoàn chỉnh
main đọc hai số rồi đọc ma trận. Nếu vuông và nhỏ thì gọi sub1, còn lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int R, C; // R hang, C cot
int a[1005][1005];
// Sub 1: mo phong di theo vong xoan, gap bien hoac o da di qua thi re sang phai (dung mang danh dau)
// Dung khi ma tran vuong kich thuoc <= 5.
void sub1() {
vector<vector<int>> vis(R, vector<int>(C, 0));
int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};
int r = 0, c = 0, d = 0, total = R * C;
for (int k = 0; k < total; k++) {
cout << a[r][c] << (k + 1 < total ? " " : "\n");
vis[r][c] = 1;
if (k + 1 == total) break;
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || nr >= R || nc < 0 || nc >= C || vis[nr][nc]) {
d = (d + 1) % 4;
nr = r + dr[d];
nc = c + dc[d];
}
r = nr;
c = nc;
}
}
// Sub 2: thu hep dan bien - lay hang tren, cot phai, hang duoi, cot trai theo tung vong. O(R*C).
void sub2() {
int top = 0, bottom = R - 1, left = 0, right = C - 1;
vector<int> res;
while (top <= bottom && left <= right) {
for (int j = left; j <= right; j++) res.push_back(a[top][j]);
top++;
for (int i = top; i <= bottom; i++) res.push_back(a[i][right]);
right--;
if (top <= bottom) {
for (int j = right; j >= left; j--) res.push_back(a[bottom][j]);
bottom--;
}
if (left <= right) {
for (int i = bottom; i >= top; i--) res.push_back(a[i][left]);
left++;
}
}
for (int i = 0; i < (int)res.size(); i++)
cout << res[i] << (i + 1 < (int)res.size() ? " " : "\n");
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int x, y;
cin >> x >> y; // dong dau: x = so hang (n), y = so cot (m) theo muc Du lieu (thu nghiem)
R = x;
C = y;
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++)
cin >> a[i][j];
if (R == C && R <= 5) sub1();
else sub2();
return 0;
}
Bình luận