VMUNCH spoj – Gặm cỏ

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ỏ.

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.

#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(); }