Nguồn đề bài: http://vn.spoj.com/problems/VMUNCH/
Nội dung bài viết
1. Đề bài VMUNCH spoj
Bessie rất yêu bãi cỏ của mình và thích thú chạy về chuồng bò vào giờ vắt sữa buổi tối.
Bessie đã chia đồng cỏ của mình là 1 vùng hình chữ nhật thành các ô vuông nhỏ với R (1 <= R <= 100) hàng và C (1 <= C <= 100) cột, đồng thời đánh dấu chỗ nào là cỏ và chỗ nào là đá. Bessie đứng ở vị trí R_b,C_b và muốn ăn cỏ theo cách của mình, từng ô vuông một và trở về chuồng ở ô 1,1 ; bên cạnh đó đường đi này phải là ngắn nhất.
Bessie có thể đi từ 1 ô vuông sang 4 ô vuông khác kề cạnh.
Dưới đây là một bản đồ ví dụ [với đá (‘*’), cỏ (‘.’), chuồng bò (‘B’), và Bessie (‘C’) ở hàng 5, cột 6] và một bản đồ cho biết hành trình tối ưu của Bessie, đường đi được dánh dấu bằng chữ ‘m’.
1 2 3 4 5 6 7 8 9 | Bản đồ Đường đi tối ưu 1 2 3 4 5 6 <-cột 1 2 3 4 5 6 <-cột 1 B . . . * . 1 B m m m * . 2 . . * . . . 2 . . * m m m 3 . * * . * . 3 . * * . * m 4 . . * * * . 4 . . * * * m 5 * . . * . C 5 * . . * . m Bessie ăn được 9 ô cỏ. |
Cho bản đồ, hãy tính xem có bao nhiêu ô cỏ mà Bessie sẽ ăn được trên con đường ngắn nhất trở về chuồng (tất nhiên trong chuồng không có cỏ đâu nên đừng có tính nhé)
Dữ liệu
- Dòng 1: 2 số nguyên cách nhau bởi dấu cách: R và C
- Dòng 2..R+1: Dòng i+1 mô tả dòng i với C ký tự (và không có dấu cách) như đã nói ở trên.
Kết quả
- Dòng 1: Một số nguyên là số ô cỏ mà Bessie ăn được trên hành trình ngắn nhất trở về chuồng.
Ví dụ
Dữ liệu
5 6
B…*.
..*…
.**.*.
..***.
*..*.C
Kết quả
9
2. Hướng dẫn VMUNCH spoj
Dùng BFS để tìm đường đi ngắn nhất đến ô (1;1). bên cạnh đó xây dựng 1 mảng để truy vết. tham khảo code sẽ hiểu rõ.
3. code tham khảo VMUNCH spoj (pascal, c++)
pascal
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 | program vmunch; const fi=''; nmax=1000; cld:array[1..4] of shortint=(0,0,1,-1); clc:array[1..4] of shortint=(1,-1,0,0); type matran=array[0..nmax+1,0..nmax+1] of longint; var a:matran; m,n:longint; f:text; dong,cot:byte; QX,QY:array[1..nmax*nmax] of longint; C:array[1..nmax*nmax] of longint; dau,cuoi:longint; procedure xuat; var i,j:word; begin for i:=1 to n do begin for j:=1 to n do write(a[i,j]:3); writeln; end; for i:=1 to cuoi do write(c[i],' '); writeln; end; procedure docfile; var i,j:byte; s:char; begin assign(f,fi); reset(f); readln(f,m,n); a[1,1]:=0; for i:=0 to m+1 do for j:=0 to n+1 do a[i,j]:=1; a[1,1]:=0; for i:=1 to m do begin for j:=1 to n do begin read(f,s); if s='.' then a[i,j]:=0 else if s='C' then begin dong:=i; cot:=j; a[i,j]:=0; end; end; readln(f); end; close(f); end; function empty:boolean; begin exit(dau>cuoi); end; procedure them(x,y:byte); begin inc(cuoi); qx[cuoi]:=x; qy[cuoi]:=y; end; procedure layra(var x,y:byte); begin x:=qx[dau]; y:=qy[dau]; inc(dau); end; procedure BFS; var i:byte; x,y:byte; x1,y1,k:byte; begin fillchar(C,sizeof(c),0); Fillchar(qy,sizeof(qy),0); Fillchar(qx,sizeof(qx),0); dau:=1; cuoi:=0; them(1,1); c[1]:=1; a[1,1]:=1; while not (dau>cuoi) do begin layra(x,y); For k:=1 to 4 do if a[x+cld[k],y+clc[k]]=0 then begin a[x+cld[k],y+clc[k]]:=c[dau-1]+1; them(x+cld[k],y+clc[k]); c[cuoi]:=c[dau-1]+1; End; end; writeln(a[dong,cot]-1); end; begin docfile; BFS; readln; end. |
c++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 | #include <bits/stdc++.h> using namespace std; const int maxn=101; int R,C; bool a[maxn][maxn]; int xb,yb,xc,yc; class Node { public: int x,y,d; Node(int x, int y, int d) { this->x=x; this->y=y; this->d=d; } }; void Init() { char ch; cin>>R>>C; for (int i=0;i<R;i++) { for (int j=0;j<C;j++) { cin>>ch; if(ch=='B') { xb=i; yb=j; a[i][j]=true; } if(ch=='C') { xc=i; yc=j; a[i][j]=false; } if(ch=='.') a[i][j]=true; if(ch=='*') a[i][j]=false; } } } void Solve() { int res=10e8; int dx[]={1,-1,0,0}; int dy[]={0,0,1,-1}; queue<Node> que; que.push(Node(xc,yc,1)); while(!que.empty()) { Node t=que.front(); que.pop(); if(t.x==xb && t.y==yb) res=min(res,t.d); else { for (int i=0;i<4;i++) { int x=t.x+dx[i]; int y=t.y+dy[i]; if(a[x][y] && x>=0 && x<R && y>=0 && y<C) { que.push(Node(x,y,t.d+1)); a[x][y]=false; } } } } cout<<res-1; } int main() { Init(); Solve(); } |
BCMUNCH ptit spoj
Bài viết liên quan
- BCACM11D spoj PTIT – Đường nguyên tố
- BCISLAND PTIT spoj – Nước biển
- PTIT016E spoj PTIT – ACM PTIT 2016 E – Kỳ thi ACM/ICPC
- TNHWIFI spoj – Cafe wifi
- P156SUME spoj PTIT – ROUND 6E – Ước chung của chuỗi
- P156SUMH spoj PTIT – ROUND 6H – Kim cương
- V8ORG spoj – Tổ chức đối lập
- LEM3 spoj – TRIP
- BCROBOT spoj PTIT – Đường đi rô-bốt
- BCLKCOUN spoj PTIT – Đếm số ao