VMUNCH spoj - Gặm cỏ - Kiến Thức 24h

Nguồn đề bài: http://vn.spoj.com/problems/VMUNCH/

Nội dung bài viết

1. Đề bài VMUNCH spoj
2. Hướng dẫn VMUNCH spoj
3. code tham khảo VMUNCH spoj (pascal, c++)
- pascal
- c++

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

           Bản đồ               Đường đi tối ưu
        1 2 3 4 5 6  &lt;-cột      1 2 3 4 5 6  &lt;-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ỏ.

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

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.

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;

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++

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

#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

VMUNCH spoj – Gặm cỏ

1. Đề bài VMUNCH spoj

Dữ liệu

Kết quả

Ví dụ

2. Hướng dẫn VMUNCH spoj

3. code tham khảo VMUNCH spoj (pascal, c++)

pascal

c++

Bài viết liên quan

Trả lời Hủy