Hướng dẫn cho PVH0I3 - Bài 4: Robot dịch chuyển
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
Trường hợp đặc biệt
Khi không tồn tại đường đi từ \(S\) tới \(E\) theo bốn hướng kề cạnh (do có vật cản), cần in ra \(-1\). Có thể dùng BFS/DFS để xử lý riêng trường hợp này, chung cho mọi subtask.
Subtask \(1\) (\(25\%\) số điểm): \(m = 1\).
Tutorial
Ta chỉ quan tâm tới các lệnh L, R vì U, D, H chắc chắn sẽ không làm robot dịch chuyển.
Đặt \(dp(i,x)\) là xét trong \(i\) kí tự đầu của \(C\), để robot dừng tại \((1,x)\) thì cần tối thiểu bao nhiêu phép biến đổi?
Chuyển trạng thái:
- Xóa: Giả sử xóa đoạn \([i+1,j]\), vậy thì có thể duyệt \(j (j > i)\) và cập nhật \(dp(j,x)\) bởi \(dp(i,x) + 1\) trong \(O(|C|)\)
- Sửa: Ta chỉ sửa thành
LhoặcR. Từ \(dp(i,x)\) cập nhật đến \(dp(i+1,x+1)\) hoặc \(dp(i+1,x-1)\) - Chèn: nhận thấy mỗi lần chèn vào sau vị trí \(i\) ta sẽ chèn những kí tự giống nhau.
Tạo thêm một mảng tương tự để truy vết. Ta sẽ chỉnh sửa chuỗi lệnh \(C\) từ sau ra trước vì việc thêm/ xóa ở đằng sau không ảnh hưởng tới chỉ số của những kí tự trước đó.
Độ phức tạp: \(\mathcal{O}(|C|n(|C|+n))\)
Solution
C++
#include<bits/stdc++.h>
using namespace std;
typedef long long Int;
const int C = 305;
const int N = 180;
int theta, m,n;
char board[N][N];
string command;
int len;
void readInput() {
cin >> theta >> m >> n;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
cin >> board[i][j];
cin >> command;
len = command.size();
command = "." + command; //lệnh đầu tiên ở chỉ số 1
}
const int INF = 1e9;
bool minimized(int& var, int val) {
if (val < var) {
var = val;
return true;
}
return false;
}
int dp[C][N];
pair<int,int> trace[C][N]; char ch[C][N];
void solve() {
int S,E;
for (int i = 1; i <= n; i++) {
if (board[1][i] == 'S') S = i;
if (board[1][i] == 'E') E = i;
}
//phần quy hoạch động
for (int i = 0; i <= len; i++)
for (int x = 0; x <= n+1; x++) {
trace[i][x] = {-1,-1};
dp[i][x] = INF;
}
dp[0][S] = 0;
for (int i = 0; i <= len; i++) {
//chèn R
for (int x = 1; x < n; x++) {
if (board[1][x+1] == '#') continue;
if (minimized(dp[i][x+1], dp[i][x] + 1))
trace[i][x+1] = {i,x};
}
//chèn L
for (int x = n; x > 1; x--) {
if (board[1][x-1] == '#') continue;
if (minimized(dp[i][x-1], dp[i][x] + 1))
trace[i][x-1] = {i,x};
}
for (int x = 1; x <= n; x++) {
if (dp[i][x] >= INF) continue;
//xóa đoạn [i+1,j]
for (int j = i+1; j <= len; j++)
if (minimized(dp[j][x], dp[i][x] + 1))
trace[j][x] = {i,x};
//sửa thành R
if (i == len) continue;
int xx = x+1;
if (xx > n || board[1][xx] == '#') --xx;
if (minimized(dp[i+1][xx], dp[i][x] + (command[i+1] != 'R'))) {
ch[i+1][xx] = 'R';
trace[i+1][xx] = {i,x};
}
//sửa thành L
xx = x-1;
if (xx < 1 || board[1][xx] == '#') ++xx;
if (minimized(dp[i+1][xx], dp[i][x] + (command[i+1] != 'L'))) {
ch[i+1][xx] = 'L';
trace[i+1][xx] = {i,x};
}
//giữ nguyên (nếu khác LR)
if (command[i+1] != 'L' && command[i+1] != 'R')
if (minimized(dp[i+1][x], dp[i][x])) {
ch[i+1][x] = command[i+1];
trace[i+1][x] = {i,x};
}
}
}
int ans = dp[len][E];
if (ans >= INF) {
cout << -1;
return ;
}
//phần truy vết
cout << ans << '\n';
for (int i = len, x = E; i > 0 || x != S; ) {
auto [ii, xx] = trace[i][x];
if (ii == i) {
cout << "INS " << i << ' ' << (x > xx ? 'R' : 'L') << '\n';
}
else if (xx == x && dp[ii][xx]+1 == dp[i][x]) {
cout << "DEL " << ii+1 << ' ' << i << '\n';
}
else if (ch[i][x] != command[i]) {
cout << "REP " << i << ' ' << ch[i][x] << '\n';
}
i = ii; x = xx;
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#define task "dichuyen"
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
readInput();
solve();
}
Subtask \(2\) (\(15\%\) số điểm): \(C\) chỉ chứa H.
Tutorial
Dễ thấy xóa các kí tự H không mang lại lợi ích gì. Để việc truy vết được đơn giản, thay vì thay đổi các lệnh H, ta chỉ việc chèn thêm các lệnh di chuyển mới vào cuối xâu.
Nhận thấy đây chính là bài toán tìm đường đi ngắn nhất từ S tới E. Dùng BFS.
Độ phức tạp: \(\mathcal{O}(mn)\)
Solution
C++
#include<bits/stdc++.h>
using namespace std;
typedef long long Int;
const int N = 180;
int theta, m,n;
char board[N][N];
string command;
int len;
void readInput() {
cin >> theta >> m >> n;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
cin >> board[i][j];
cin >> command;
len = command.size();
}
int label[N][N];
int trace[N][N];
typedef pair<int,int> Cell;
#define x first
#define y second
const string directions = "UDLR";
const int xD[] = {-1,+1, 0, 0};
const int yD[] = { 0, 0,-1,+1};
string bfs(Cell S, Cell E) {
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
label[i][j] = -1;
label[S.x][S.y] = 0;
queue<Cell> qu;
qu.push(S);
while (!qu.empty()) {
Cell u = qu.front(); qu.pop();
for (int d = 0; d < 4; d++) {
Cell v(u.x + xD[d], u.y + yD[d]);
if (v.x < 1 || v.x > m || v.y < 1 || v.y > n) continue;
if (board[v.x][v.y] == '#' || label[v.x][v.y] != -1) continue;
label[v.x][v.y] = label[u.x][u.y] + 1;
trace[v.x][v.y] = d;
qu.push(v);
}
}
if (label[E.x][E.y] == -1) return "-1";
string path;
while (E.x != S.x || E.y != S.y) {
int d = trace[E.x][E.y];
path += directions[d];
E.x -= xD[d];
E.y -= yD[d];
}
reverse(path.begin(), path.end());
return path;
}
void solve() {
int Sx, Sy, Ex, Ey;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) {
if (board[i][j] == 'S') Sx = i, Sy = j;
if (board[i][j] == 'E') Ex = i, Ey = j;
}
string path = bfs(Cell(Sx,Sy), Cell(Ex,Ey));
if (path[0] == '-') {
cout << path;
return ;
}
cout << path.size() << '\n';
for (auto c : path) {
cout << "INS " << len << ' ' << c << '\n';
++len;
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#define task "dichuyen"
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
readInput();
solve();
}
Subtask \(4\) (\(15\%\) số điểm): \(m,n \le 20\) và \(|C| \le 50\).
Tutorial
Đặt \(dp(i,x,y)\) là xét trong \(i\) lệnh đầu của \(C\), để robot đứng tại \((x,y)\), thì cần tối thiểu bao nhiêu phép biến đổi?
Chuyển trạng thái:
- Xóa: giống subtask 1.
- Sửa (hoặc giữ nguyên): xét \(5\) lệnh có thể cho vị trí thứ \(i\), và mô phỏng lại bước di chuyển đó để có vị trí tiếp theo là \((u,v)\). Từ \(dp(i,x,y)\) ta cập nhật \(dp(i+1,u,v)\).
- Chèn: tính trước khoảng cách từ mỗi ô tới tất cả ô còn lại trong \(O((mn)^2)\). Từ \(dp(i,x,y)\) ta cập nhật cho \(dp(i,u,v)\).
Cần lưu thêm một mảng khác để truy vết. Mảng này lưu thông tin: để đi tới đáp án tối ưu ở trạng thái hiện tại, trước đó tôi đã ở trạng thái nào?
Độ phức tạp là \(\mathcal{O}((|C|^2 \cdot mn + |C| \cdot (mn)^2)\)
Solution
C++
#include<bits/stdc++.h>
using namespace std;
typedef long long Int;
const int C = 55;
const int N = 23; //giới hạn nhỏ để khai báo mảng label & trace
int theta, m,n;
char board[N][N];
string command;
int len;
void readInput() {
cin >> theta >> m >> n;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
cin >> board[i][j];
cin >> command;
len = command.size();
command = "." + command; //lệnh đầu tiên ở chỉ số 1
}
typedef pair<int,int> Cell;
#define x first
#define y second
const string directions = "UDLRH";
const int xD[] = {-1,+1, 0, 0,+0};
const int yD[] = { 0, 0,-1,+1,+0};
bool move(Cell& u, int d) { //sẽ dùng lại ở hàm QHĐ
Cell v(u.x + xD[d], u.y + yD[d]);
if (v.x < 1 || v.x > m || v.y < 1 || v.y > n) return false;
if (board[v.x][v.y] == '#') return false;
u = v;
return true;
}
void bfs(Cell S, int label[][N], int trace[][N]) {
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
label[i][j] = -1;
label[S.x][S.y] = 0;
queue<Cell> qu;
qu.push(S);
while (!qu.empty()) {
Cell u = qu.front(); qu.pop();
for (int d = 0; d < 4; d++) {
Cell v(u); move(v,d);
if (label[v.x][v.y] != -1) continue;
label[v.x][v.y] = label[u.x][u.y] + 1;
trace[v.x][v.y] = d;
qu.push(v);
}
}
}
int label[N][N][N][N];
int trace[N][N][N][N];
string getPath(Cell S, Cell E) {
if (label [S.x][S.y] [E.x][E.y] == -1) return "-1";
string path;
while (E.x != S.x || E.y != S.y) {
int d = trace [S.x][S.y] [E.x][E.y];
path += directions[d];
E.x -= xD[d];
E.y -= yD[d];
}
reverse(path.begin(), path.end());
return path;
}
const int INF = 1e9;
bool minimized(int& var, int val) {
if (val < var) {
var = val;
return true;
}
return false;
}
int dp[C][N][N];
struct State {
int i,x,y; char c;
State() {}
State(int i, int x, int y): i(i), x(x), y(y) {}
};
State pre[C][N][N]; //truy vết
void solve() {
int Sx, Sy, Ex, Ey;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) {
if (board[i][j] == 'S') Sx = i, Sy = j;
if (board[i][j] == 'E') Ex = i, Ey = j;
}
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
bfs(Cell(i,j), label[i][j], trace[i][j]);
if (label [Sx][Sy] [Ex][Ey] == -1) {
cout << -1;
return ;
}
//Quy hoạch động
for (int i = 0; i <= len; i++)
for (int x = 0; x <= m; x++)
for (int y = 0; y <= n; y++)
dp[i][x][y] = INF;
dp[0][Sx][Sy] = 0;
for (int i = 0; i <= len; i++) {
//chèn
for (int x = 1; x <= m; x++)
for (int y = 1; y <= n; y++)
for (int u = 1; u <= m; u++)
for (int v = 1; v <= n; v++) {
int dist = label [x][y] [u][v];
if (dist == -1) continue;
if (minimized(dp[i][u][v], dp[i][x][y] + dist))
pre[i][u][v] = State(i,x,y);
}
for (int x = 1; x <= m; x++) {
for (int y = 1; y <= n; y++) {
if (dp[i][x][y] >= INF) continue;
//xóa
for (int j = i+1; j <= len; j++)
if (minimized(dp[j][x][y], dp[i][x][y] + 1))
pre[j][x][y] = State(i,x,y);
//thay đổi
if (i == len) continue;
for (int d = 0; d < 5; d++) {
Cell u(x,y); move(u,d);
if (minimized(dp[i+1][u.x][u.y],
dp[i][x][y] + (command[i+1] != directions[d]))) {
State pr = State(i,x,y);
pr.c = directions[d];
pre[i+1][u.x][u.y] = pr;
}
}
}
}
}
if (dp[len][Ex][Ey] >= INF) {
cout << -1;
return ;
}
//Truy vết
vector<string> edits;
for (int i = len, x = Ex, y = Ey;
i > 0 || x != Sx || y != Sy; ) {
auto [ii, xx, yy, c] = pre[i][x][y];
if (i == ii) {
string path = getPath(Cell(xx,yy), Cell(x,y));
for (int j = path.size()-1; j >= 0; j--)
edits.push_back("INS " + to_string(i) + " " + path[j]);
} else {
int dpPre = dp[ii][xx][yy];
int dpCur = dp[i][x][y];
if (dpPre < dpCur) {
if (xx == x && yy == y)
edits.push_back("DEL " + to_string(ii+1) + " " + to_string(i));
else
edits.push_back("REP " + to_string(i) + " " + c);
}
}
i = ii; x = xx; y = yy;
}
cout << edits.size() << '\n';
for (auto s : edits) cout << s << '\n';
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#define task "dichuyen"
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
readInput();
solve();
}
Subtask \(5\) (\(15\%\) số điểm): \(m,n \le 50\) và \(|C| \le 100\).
Tutorial
Đặt \(dp\) giống subtask 4. Ta cần tối ưu thao tác chèn. Nhận thấy chèn này giống tìm đường đi ngắn nhất (như subtask 2), tuy nhiên một số nhãn đã có sẵn trọng số (\(dp\) tại ô đó). Có thể giải quyết được bằng cách:
- Thêm dần các đỉnh vào theo thứ tự trọng số tăng dần. Bạn có thể tham khảo bài Spell - DHBB.
- Dùng Dijkstra, ĐPT lớn hơn chút nhưng quen thuộc & dễ code.
Độ phức tạp: \(\mathcal{O}(|C|^2 \cdot mn + |C| \cdot mn\log)\)
Solution
C++
#include<bits/stdc++.h>
using namespace std;
typedef long long Int;
//giới hạn của sub 5
const int C = 105;
const int N = 55;
int theta, m,n;
char board[N][N];
string command;
int len;
void readInput() {
cin >> theta >> m >> n;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
cin >> board[i][j];
cin >> command;
len = command.size();
command = "." + command; //lệnh đầu tiên ở chỉ số 1
}
const int INF = 1e9;
bool minimized(int& var, int val) {
if (val < var) {
var = val;
return true;
}
return false;
}
int dp[C][N][N];
struct State {
int i,x,y; char c;
State() {}
State(int i, int x, int y): i(i), x(x), y(y) {}
};
State pre[C][N][N]; //truy vết
typedef pair<int,int> Cell;
#define x first
#define y second
const string directions = "UDLRH";
const int xD[] = {-1,+1, 0, 0,+0};
const int yD[] = { 0, 0,-1,+1,+0};
bool move(Cell& u, int d) { //sẽ dùng lại ở hàm QHĐ
Cell v(u.x + xD[d], u.y + yD[d]);
if (v.x < 1 || v.x > m || v.y < 1 || v.y > n) return false;
if (board[v.x][v.y] == '#') return false;
u = v;
return true;
}
void bfs(int p) {
auto cmp = [=] (Cell u, Cell v) {
return dp[p][u.x][u.y] > dp[p][v.x][v.y];
};
vector<Cell> nodes;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) {
if (dp[p][i][j] < INF)
nodes.push_back(Cell(i,j));
}
sort(nodes.begin(), nodes.end(), cmp);
if (nodes.empty()) return ;
queue<Cell> qu;
int curWeight = 0;
while (!qu.empty() || !nodes.empty()) {
Cell u;
if (qu.empty()) {
u = nodes.back();
curWeight = dp[p][u.x][u.y];
}
while (!nodes.empty()) {
u = nodes.back();
if (dp[p][u.x][u.y] > curWeight) break;
qu.push(u);
nodes.pop_back();
}
u = qu.front(); qu.pop();
for (int d = 0; d < 4; d++) {
Cell v(u); move(v,d);
if (minimized(dp[p][v.x][v.y], dp[p][u.x][u.y] + 1)) {
curWeight = dp[p][v.x][v.y];
State trace(p, u.x, u.y);
trace.c = directions[d];
pre[p][v.x][v.y] = trace;
qu.push(v);
}
}
}
}
void solve() {
int Sx, Sy, Ex, Ey;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) {
if (board[i][j] == 'S') Sx = i, Sy = j;
if (board[i][j] == 'E') Ex = i, Ey = j;
}
//Quy hoạch động
for (int i = 0; i <= len; i++)
for (int x = 0; x <= m; x++)
for (int y = 0; y <= n; y++)
dp[i][x][y] = INF;
dp[0][Sx][Sy] = 0;
for (int i = 0; i <= len; i++) {
bfs(i); //chèn
for (int x = 1; x <= m; x++) {
for (int y = 1; y <= n; y++) {
if (dp[i][x][y] >= INF) continue;
//xóa
for (int j = i+1; j <= len; j++)
if (minimized(dp[j][x][y], dp[i][x][y] + 1))
pre[j][x][y] = State(i,x,y);
//thay đổi
if (i == len) continue;
for (int d = 0; d < 5; d++) {
Cell u(x,y); move(u,d);
if (minimized(dp[i+1][u.x][u.y],
dp[i][x][y] + (command[i+1] != directions[d]))) {
State pr = State(i,x,y);
pr.c = directions[d];
pre[i+1][u.x][u.y] = pr;
}
}
}
}
}
if (dp[len][Ex][Ey] >= INF) {
cout << -1;
return ;
}
//Truy vết
vector<string> edits;
for (int i = len, x = Ex, y = Ey;
i > 0 || x != Sx || y != Sy; ) {
auto [ii, xx, yy, c] = pre[i][x][y];
if (i == ii) {
edits.push_back("INS " + to_string(i) + " " + c);
} else {
int dpPre = dp[ii][xx][yy];
int dpCur = dp[i][x][y];
if (dpPre < dpCur) {
if (xx == x && yy == y)
edits.push_back("DEL " + to_string(ii+1) + " " + to_string(i));
else
edits.push_back("REP " + to_string(i) + " " + c);
}
}
i = ii; x = xx; y = yy;
}
cout << edits.size() << '\n';
for (auto s : edits) cout << s << '\n';
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#define task "dichuyen"
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
readInput();
solve();
}
Subtask \(3\) (\(15\%\) số điểm): Dữ liệu vào đảm bảo tồn tại một phương án biến đổi tối ưu mà không cần sử dụng phép biến đổi DEL (xoá một đoạn liên tiếp):
Tutorial
Ý tưởng vẫn giống như subtask 5, vì không có thao tác xóa nên không mất thêm \(O(C)\) chuyển trạng thái.
Nhận thấy đáp án (giá trị của \(dp\)) rơi vào tầm \(O(mn)\) nên có thể sắp xếp bằng đếm phân phối để giảm bớt ĐPT \(\log\).
Độ phức tạp: \(\mathcal{O}(|C|mn)\)
Solution
C++
#include<bits/stdc++.h>
using namespace std;
typedef long long Int;
const int C = 305;
const int N = 180;
int theta, m,n;
char board[N][N];
string command;
int len;
void readInput() {
cin >> theta >> m >> n;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
cin >> board[i][j];
cin >> command;
len = command.size();
command = "." + command; //lệnh đầu tiên ở chỉ số 1
}
const int INF = 1e9;
bool minimized(int& var, int val) {
if (val < var) {
var = val;
return true;
}
return false;
}
int dp[C][N][N];
struct State {
int i,x,y; char c;
State() {}
State(int i, int x, int y): i(i), x(x), y(y) {}
};
State pre[C][N][N]; //truy vết
typedef pair<int,int> Cell;
#define x first
#define y second
const string directions = "UDLRH";
const int xD[] = {-1,+1, 0, 0,+0};
const int yD[] = { 0, 0,-1,+1,+0};
bool move(Cell& u, int d) { //sẽ dùng lại ở hàm QHĐ
Cell v(u.x + xD[d], u.y + yD[d]);
if (v.x < 1 || v.x > m || v.y < 1 || v.y > n) return false;
if (board[v.x][v.y] == '#') return false;
u = v;
return true;
}
void bfs(int p) {
const int limit = 2*m*n;
vector<Cell> nodes[limit + 5];
int remaining = 0;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) {
if (dp[p][i][j] <= limit) {
nodes[dp[p][i][j]].push_back(Cell(i,j));
++remaining;
}
}
if (!remaining) return ;
queue<Cell> qu;
int curWeight = 0;
while (!qu.empty() || remaining) {
if (qu.empty()) {
while (nodes[curWeight].empty()) ++curWeight;
}
for (auto u : nodes[curWeight]) {
--remaining;
qu.push(u);
}
nodes[curWeight].clear();
Cell u = qu.front(); qu.pop();
for (int d = 0; d < 4; d++) {
Cell v(u); move(v,d);
if (minimized(dp[p][v.x][v.y], dp[p][u.x][u.y] + 1)) {
curWeight = dp[p][v.x][v.y];
State trace(p, u.x, u.y);
trace.c = directions[d];
pre[p][v.x][v.y] = trace;
qu.push(v);
}
}
}
}
void solve() {
int Sx, Sy, Ex, Ey;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) {
if (board[i][j] == 'S') Sx = i, Sy = j;
if (board[i][j] == 'E') Ex = i, Ey = j;
}
//Quy hoạch động
for (int i = 0; i <= len; i++)
for (int x = 0; x <= m; x++)
for (int y = 0; y <= n; y++)
dp[i][x][y] = INF;
dp[0][Sx][Sy] = 0;
for (int i = 0; i <= len; i++) {
bfs(i); //chèn
for (int x = 1; x <= m; x++) {
for (int y = 1; y <= n; y++) {
if (dp[i][x][y] >= INF) continue;
//thay đổi
if (i == len) continue;
for (int d = 0; d < 5; d++) {
Cell u(x,y); move(u,d);
if (minimized(dp[i+1][u.x][u.y],
dp[i][x][y] + (command[i+1] != directions[d]))) {
State pr = State(i,x,y);
pr.c = directions[d];
pre[i+1][u.x][u.y] = pr;
}
}
}
}
}
if (dp[len][Ex][Ey] >= INF) {
cout << -1;
return ;
}
//Truy vết
vector<string> edits;
for (int i = len, x = Ex, y = Ey;
i > 0 || x != Sx || y != Sy; ) {
auto [ii, xx, yy, c] = pre[i][x][y];
if (i == ii) {
edits.push_back("INS " + to_string(i) + " " + c);
} else {
int dpPre = dp[ii][xx][yy];
int dpCur = dp[i][x][y];
if (dpPre < dpCur) {
if (xx == x && yy == y)
edits.push_back("DEL " + to_string(ii+1) + " " + to_string(i));
else
edits.push_back("REP " + to_string(i) + " " + c);
}
}
i = ii; x = xx; y = yy;
}
cout << edits.size() << '\n';
for (auto s : edits) cout << s << '\n';
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#define task "dichuyen"
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
readInput();
solve();
}
Bonus
Nếu không có \(\theta\), để biết được test có thuộc subtask 3 hay không thì không có cách nào khác ngoài việc ta phải tìm ra chính xác đáp án, rồi mới kiểm chứng được là có cần DEL hay không. Vì có khả năng là tồn tại đường đi nhưng cách giải của subtask 3 cho ra -1. Hoặc đưa ra được phương án nhưng chưa tối ưu.
Với bộ test của GS.PVH thì code này vẫn ăn được phần lớn.
Subtask \(6\) (\(20\%\) số điểm): không có ràng buộc gì thêm.
Tutorial
Thao tác xóa thật ra không quá phức tạp. Chỉ cần lưu thêm một chiều \(dp\) (0/1) là thao tác cuối cùng có phải là thao tác xóa không? (vì thực tế không cần quan tâm độ dài của đoạn được xóa).
Độ phức tạp: \(\mathcal{O}(|C|mn)\)
Solution
C++
#include<bits/stdc++.h>
using namespace std;
typedef long long Int;
const int C = 305;
const int N = 180;
int theta, m,n;
char board[N][N];
string command;
int len;
void readInput() {
cin >> theta >> m >> n;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
cin >> board[i][j];
cin >> command;
len = command.size();
command = "." + command; //lệnh đầu tiên ở chỉ số 1
}
const int INF = 1e9;
bool minimized(int& var, int val) {
if (val < var) {
var = val;
return true;
}
return false;
}
int dp[C][2][N][N]; //0/1: có xóa hay không
struct State {
int i; bool b; int x,y; char c;
State() {}
State(int i, bool b, int x, int y): i(i), b(b), x(x), y(y) {}
};
State pre[C][2][N][N]; //truy vết
typedef pair<int,int> Cell;
#define x first
#define y second
const string directions = "UDLRH";
const int xD[] = {-1,+1, 0, 0,+0};
const int yD[] = { 0, 0,-1,+1,+0};
bool move(Cell& u, int d) { //sẽ dùng lại ở hàm QHĐ
Cell v(u.x + xD[d], u.y + yD[d]);
if (v.x < 1 || v.x > m || v.y < 1 || v.y > n) return false;
if (board[v.x][v.y] == '#') return false;
u = v;
return true;
}
void bfs(int p) {
const int limit = m*n;
vector<Cell> nodes[limit + 5];
int remaining = 0;
for (int b : {0,1})
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) {
if (dp[p][b][i][j] <= limit) {
nodes[dp[p][b][i][j]].push_back(Cell(i + b*m, j));
++remaining;
}
}
if (!remaining) return ;
queue<Cell> qu;
int curWeight = 0;
while (!qu.empty() || remaining) {
if (qu.empty()) {
while (nodes[curWeight].empty()) ++curWeight;
}
for (auto u : nodes[curWeight]) {
--remaining;
qu.push(u);
}
nodes[curWeight].clear();
Cell u = qu.front(); qu.pop();
int b = 0;
if (u.x > m) {
b = 1;
u.x -= m;
}
for (int d = 0; d < 4; d++) {
Cell v(u); move(v,d);
if (minimized(dp[p][0][v.x][v.y], dp[p][b][u.x][u.y] + 1)) {
curWeight = dp[p][0][v.x][v.y];
State trace(p, b, u.x, u.y);
trace.c = directions[d];
pre[p][0][v.x][v.y] = trace;
qu.push(v);
}
}
}
}
void solve() {
int Sx, Sy, Ex, Ey;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) {
if (board[i][j] == 'S') Sx = i, Sy = j;
if (board[i][j] == 'E') Ex = i, Ey = j;
}
//Quy hoạch động
for (int i = 0; i <= len; i++)
for (int b : {0,1})
for (int x = 0; x <= m; x++)
for (int y = 0; y <= n; y++)
dp[i][b][x][y] = INF;
dp[0][0][Sx][Sy] = 0;
for (int i = 0; i <= len; i++) {
bfs(i); //chèn
for (int b : {0,1}) {
for (int x = 1; x <= m; x++) {
for (int y = 1; y <= n; y++) {
if (dp[i][b][x][y] >= INF) continue;
//xóa
if (minimized(dp[i+1][1][x][y], dp[i][b][x][y] + (b==0))) {
pre[i+1][1][x][y] = (b == 1) ? pre[i][b][x][y] : State(i,b,x,y);
}
//thay đổi
if (i == len) continue;
for (int d = 0; d < 5; d++) {
Cell u(x,y); move(u,d);
if (minimized(dp[i+1][0][u.x][u.y],
dp[i][b][x][y] + (command[i+1] != directions[d]))) {
State pr = State(i,b,x,y);
pr.c = directions[d];
pre[i+1][0][u.x][u.y] = pr;
}
}
}
}
}
}
int b = 0;
if (dp[len][1][Ex][Ey] < dp[len][0][Ex][Ey])
b = 1;
if (dp[len][b][Ex][Ey] >= INF) {
cout << -1;
return ;
}
//Truy vết
vector<string> edits;
for (int i = len, x = Ex, y = Ey;
i > 0 || b != 0 || x != Sx || y != Sy;) {
auto [ii, bb, xx, yy, c] = pre[i][b][x][y];
if (i == ii) {
edits.push_back("INS " + to_string(i) + " " + c);
} else {
int dpPre = dp[ii][bb][xx][yy];
int dpCur = dp[i][b][x][y];
if (dpPre < dpCur) {
if (b)
edits.push_back("DEL " + to_string(ii+1) + " " + to_string(i));
else
edits.push_back("REP " + to_string(i) + " " + c);
}
}
i = ii; b = bb; x = xx; y = yy;
}
cout << edits.size() << '\n';
for (auto s : edits) cout << s << '\n';
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#define task "dichuyen"
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
readInput();
solve();
}
Bình luận