Bài toán
Cho một bản đồ gồm m*n ô. Mỗi ô có thể là một trong các giá trị:
- '*': Ô này có nước ngập.
- 'X': Núi đá.
- '.': Đất liền (đất chưa bị ngập).
- 'S': Nơi cô gái đang đứng (tất nhiên là không bị ngập).
- 'D': Nhà của cô gái.
Mỗi phút, cô gái có thể di chuyển đến một trong bốn ô mà có kiểu đất liền hoặc nhà mà kề cạnh với ô cô đang đứng. Mỗi phút thì ô có nước ngập sẽ chảy nước lan sang 4 ô là đất liền ở xung quanh (tức 4 ô kề cạnh). Nước không thể chảy vào ô núi đá và nhà của cô gái hoặc chảy ra ngoài biên. Cô gái không thể đi vào ô núi đá hoặc ô mà đã bị ngập nước, cô không thể chạy ra ngoài biên. Ở một phút, cô gái di chuyển trước, nước chảy sau. Thế nên cô có thể đi vào ô sắp bị ngập nhưng chưa ngập. Yêu cầu bài toán là xác định xem cô có thể đi về đến nhà được hay không, nếu được thì thời gian ngắn nhất là bao nhiêu.
Input
Dòng 1 gồm hai số nguyên dương m và n (0<m,n<=50).
m dòng tiếp theo mỗi dòng có n kí tự là một trong số các kí tự '*','X','.','S','D'. Mỗi kí tự S và D chỉ xuất hiện chính xác một lần.
Output
Nếu không về được thì in ra KAKTUS. Nếu về được thì in ra thời gian ngắn nhất (số phút) để cô ấy về được đến nhà.
Code này của Nguyễn Tiến Trung Kiên
#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int, int> ii;
#define X first
#define Y second
bool minimize(int &a, int b){ if (a>b) a=b; else return false; return true; }
int m, n;
char a[123][123];
int water_time[123][123];
int woman_time[123][123];
int rx[]={-1,0,0,1};
int ry[]={0,-1,1,0};
void water_bfs(){
queue<ii> qu;
int i, j; ii u, v;
for (i=1; i<=m; i++)
for (j=1; j<=n; j++)
if (a[i][j]=='*'){
qu.push(ii(i,j));
water_time[i][j]=1;
}
else water_time[i][j]=0x77778888;
while (qu.size()){
u=qu.front(); qu.pop();
for (i=0; i<=3; i++){
v.X=u.X+rx[i];
v.Y=u.Y+ry[i];
if (v.X<1 or v.X>m or v.Y<1 or v.Y>n) continue;
if (a[v.X][v.Y]!='.' && a[v.X][v.Y]!='S') continue;
if (minimize(water_time[v.X][v.Y], water_time[u.X][u.Y]+1))
qu.push(v);
}
}
}
int woman_bfs(ii start, ii target){
queue<ii> qu;
int i, j; ii u, v;
for (i=1; i<=m; i++)
for (j=1; j<=n; j++)
woman_time[i][j]=0x77778888;
qu.push(start);
woman_time[start.X][start.Y]=1;
while (qu.size()){
u=qu.front(); qu.pop();
if (u==target) return woman_time[u.X][u.Y];
for (i=0; i<=3; i++){
v.X=u.X+rx[i];
v.Y=u.Y+ry[i];
if (v.X<1 or v.X>m or v.Y<1 or v.Y>n) continue;
if (a[v.X][v.Y]!='.' && a[v.X][v.Y]!='D') continue;
if (water_time[v.X][v.Y] <= woman_time[u.X][u.Y]+1) continue;
if (minimize(woman_time[v.X][v.Y], woman_time[u.X][u.Y]+1))
qu.push(v);
}
}
return 0;
}
main(){
int i, j;
ii start, target;
scanf("%d%d", &m, &n);
for (i=1; i<=m; i++)
scanf("%s", a[i]+1);
water_bfs();
for (i=1; i<=m; i++)
for (j=1; j<=n; j++)
if (a[i][j]=='S') start=ii(i, j);
else if (a[i][j]=='D') target=ii(i,j);
int z = woman_bfs(start, target);
//for (i=1; i<=m; i++)
//for (j=1; j<=n; j++)
//printf(j==n?"%d\n":"%d ", woman_time[i][j]);
if (z==0) printf("KAKTUS\n");
else printf("%d\n", z-1);
}
Nhận xét
Mô tả
void water_bfs()
Tính các giá trị của water_time, tức là thời gian để nước tràn vào các ô.
void woman_bfs()
BFS cho cô gái, đảm bảo cô ta không đi vào vùng ngập nước.
Các lỗi thường gặp
Wrong answer
- Do viết sai điều kiện để đi của nước và của cô gái. Chú ý các chi tiết: nước không được đi vào ô D, cô gái không được đi vào vùng có nước nhưng được đi vào vùng sắp có nước.