Bài toán
Cho một bản đồ m x n, (m<=30000, n<=30) các ô có thể là ô trống '.' hoặc đá 'X'. Người ta lần lượt thả các viên bi 'O' vào vị trí x1, x2, ..., xt (1<=xi<=n) trên bản đồ, khi được thả thì viên bi sẽ rơi theo quy tắc sau:
- Nếu phía dưới viên bi là đá hoặc đáy bảng thì viên bi dừng lại.
- Ngược lại nếu phía dưới viên là ô trống thì viên bi đi vào ô trống.
- Ngược lại nếu ô bên trái và ô trái dưới trống thì viên bi đi vào ô trái dưới.
- Ngược lại nếu ô bên phải và ô phải dưới trống thì viên bi đi vào ô phải dưới.
- Ngược lại thì viên bi đúng yên.
Yêu cầu in ra trạng thái cuối cùng của bản đồ.
Độ phức tạp
O(n*(m+t))
Code này của Nguyễn Tiến Trung Kiên
#include <stdio.h>
#include <vector>
using namespace std;
int m, n;
char a[33000][31];
vector<int> b[31];
void update(vector<int> & L){
while (a[L.size()-1][L.back()] != '.') L.pop_back();
for (;;){
int x=L.size()-1, y=L.back();
if (a[x+1][y]=='X') break;
if (a[x+1][y]=='.') { L.push_back(y); continue; }
if (a[x][y-1]=='.' && a[x+1][y-1]=='.') { L.push_back(y-1); continue; }
if (a[x][y+1]=='.' && a[x+1][y+1]=='.') { L.push_back(y+1); continue; }
break;
}
}
main(){
int i, x, t;
scanf("%d%d", &m, &n);
for (i=1; i<=m; i++)
scanf("%s", a[i]+1);
for (i=1; i<=n; i++)
{ a[m+1][i]='X'; a[0][i]='.'; }
for (i=1; i<=n; i++) b[i].push_back(i);
scanf("%d", &t);
while (t--){
scanf("%d", &x);
for (i=1; i<=n; i++) update(b[i]);
a[b[x].size()-1][b[x].back()]='O';
for (i=1; i<=n; i++) update(b[i]); // it seems not necessary
}
for (i=1; i<=m; i++) printf("%s\n", a[i]+1);
}
Nhận xét
Với mỗi cột, ta lưu lại đường đi mà nó sẽ đi. Khi thả vào cột nào thì viên bi sẽ rơi vào đúng vị trí cuối của đưuòng đi. Sau khi thả thì ta phải cập nhật lại các đường đi này. Ở mỗi đường đi, sẽ có một vị trí mà tù đầu đường cho đến vị trí đó là ô trống '.', phần còn lại đều là ô đã chứa bi 'O'. Sau khi ta tìm đưuọc vị trí đấy thì dùng quy tắc rơi của viên bi để tìm tiếp đoạn đường sau vị trí đấy.