Editorial for Gặm cỏ


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

const dx:array[1..4] of shortint=(-1,0,1,0);
      dy:array[1..4] of shortint=(0,1,0,-1);
var m,n,sx,sy:byte;
    a:array[1..100,1..100] of char;
    d:array[1..100,1..100] of word;
    q:array[1..10000,0..1] of byte;

procedure wf;
begin
     write(d[1,1]-1);
end;

procedure rf;
var I,j:byte;
begin
     readln(m,n);
     for i:=1 to m do
     begin
          for j:=1 to n do
          begin
               read(a[i,j]);
               if a[i,j]='C' then
               begin
                    sx:=i; sy:=j;
               end;
          end;
          readlN;
     end;
end;

function check(x,y:byte):boolean;
begin
     check:=(x>0) and (x<=m) and (y>0) and (y<=n);
end;

procedure pr;
var i,num:integer; x,y,j:byte;
begin
     fillchar(d,sizeof(d),0);
     num:=1; i:=1; q[1,0]:=sx; q[1,1]:=sy; d[sx,sy]:=1;
     repeat
           for j:=1 to 4 do
           begin
                x:=q[i,0]+dx[j]; y:=q[i,1]+dy[j];
                if check(x,y) and ((a[x,y]='.') or (a[x,y]='B')) and (d[x,y]=0) 

then
                begin
                     inc(num);
                     q[num,0]:=x; q[num,1]:=y;
                     d[x,y]:=d[q[i,0],q[i,1]]+1;
                end;
           end;
           inc(i);
     until (d[1,1]>0);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của happyboy99x

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define sz(a) int((a).size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); it != _e; ++it)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000
#define N 1005

int r, c;
char a[N][N];
bool ch[N][N];
int I[4] = {-1, 0, 0, 1}, J[4] = {0, -1, 1, 0};

int main() {
    //freopen( "input.txt", "r", stdin );
    //freopen( "output.txt", "w", stdout );
    scanf( "%d%d\n", &r, &c );
    rep(i, r) gets(a[i]);
    queue<ii> qu;
    bool stop = false;
    for( int i = 0; i < r && !stop; ++i ) rep(j, c)
        if( a[i][j] == 'C' ) {
            ch[i][j] = 1; qu.push(mp(i,j)); stop = 1; break;
        }
    for( int step = 0; !qu.empty(); ++step ) {
        rep(i, qu.size()) {
            int x = qu.front().fi, y = qu.front().se; qu.pop();
            if( a[x][y] == 'B' ) {
                printf( "%d\n", step );
                return 0;
            }
            rep(k, 4) {
                int xx = x + I[k], yy = y + J[k];
                if( xx >= 0 && yy >= 0 && xx < r && yy < c && ch[xx][yy] == 0 && a[xx][yy] != '*') {
                    ch[xx][yy] = 1; qu.push(mp(xx,yy));
                }
            }
        }
    }
    return 0;
}

Code mẫu của ladpro98

Program VMUNCH;
Const fi='';
      fo='';
      wx:array[1..4] of integer=(-1,1,0,0);
      wy:array[1..4] of integer=(0,0,1,-1);
Var a:array[0..123,0..123] of longint;
    r,c,x,y,count:longint;
    f:text;
Procedure INPUT;
Var i,j:longint;
    t:char;
Begin
     Assign(f,fi);
     Reset(f);
     readln(f,r,c);
     For i:=0 to r+1 do
       For j:=0 to c+1 do
          a[i,j]:=1;
     a[1,1]:=0;
     For i:=1 to r do
     begin
       For j:=1 to c do
       begin
            read(f,t);
            If t='.' then a[i,j]:=0;
            If t='C' then
            begin
                 x:=i;
                 y:=j;
                 a[x,y]:=0;
            End;
       End;
       Readln(f);
     End;
     Close(f);
End;
Procedure FIND;
var dem,first,last,k,i,j:longint;
    tx,ty,c:array[1..10001] of longint;
Begin
     first:=1;
     last:=1;
     Fillchar(tx,sizeof(tx),0);
     Fillchar(ty,sizeof(ty),0);
     Fillchar(c,sizeof(c),0);
     tx[1]:=1;ty[1]:=1;a[1,1]:=1;c[1]:=1;
     dem:=0;
     While first<=last do
     begin
          i:=tx[first];
          j:=ty[first];
          For k:=1 to 4 do
            if a[i+wx[k],j+wy[k]]=0 then
            begin
                 a[i+wx[k],j+wy[k]]:=c[first]+1;
                 inc(last);
                 tx[last]:=i+wx[k];
                 ty[last]:=j+wy[k];
                 c[last]:=c[first]+1;
                 If a[x,y]<>0 then
                 begin
                      count:=a[x,y]-1;
                      Exit;
                 End;
            End;
          inc(first);
     End;
End;
Procedure OUTPUT;
Begin
     Assign(f,fo);
     Rewrite(f);
     Writeln(f,count);
     Close(f);
End;
BEGIN
     INPUT;
     FIND;
     OUTPUT;
END.

Code mẫu của RR

uses math;
const
  MAXN=111;

var
  m,n,i,j,su,sv,tu,tv,u,v,uu,vv,di,dj:longint;
  a:array[1..MAXN,1..MAXN] of char;
  d:array[1..MAXN,1..MAXN] of longint;
  qu,qv:array[1..MAXN*MAXN] of longint;
  first,last:longint;

begin
  readln(m,n);
  for i:=1 to m do
    begin
      for j:=1 to n do
        begin
          read(a[i,j]);
          if a[i,j]='B' then begin tu:=i; tv:=j; end;
          if a[i,j]='C' then begin su:=i; sv:=j; end;
        end;
      readln;
    end;

  first:=1; last:=1; qu[1]:=su; qv[1]:=sv; d[su,sv]:=1;
  while first<=last do
    begin
      u:=qu[first]; v:=qv[first]; inc(first);
      for di:=-1 to 1 do
      for dj:=-1 to 1 do
        if di*di+dj*dj=1 then
          begin
            uu:=u+di; vv:=v+dj;
            if (uu>0) and (vv>0) and (uu<=m) and (vv<=n) and (d[uu,vv]=0)
            and (a[uu,vv]<>'*') then
              begin
                d[uu,vv]:=d[u,v]+1;
                inc(last); qu[last]:=uu; qv[last]:=vv;
              end;
          end;
    end;

  writeln(d[tu,tv]-1);
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>

int n,m,a[101][101],f[101][101],x1,y1,x2,y2,so = 1,x[10001],y[10001];
char s[101][101];
int check(int u,int v)
{
    if(u>=0 && u<n && v>=0 && v<m && a[u][v]==0)
     return 1;
     else return 0;
  //   printf("%d %d %d %d\n",u,v,n,m);
}

int xuly(int j,int i)
{
     int u,v;
     v = j-1;u = i;
     if( check(u,v) == 1) 
     {
         f[u][v] = f[i][j]+1;
         a[u][v]=1;
         so++;
         x[so] = v;
         y[so] = u;
         //printf("",so);
        // printf("%d %d %d\n",so,u,v);
     }
     v = j+1;u = i;
     if( check(u,v) == 1) 
     {

         f[u][v] = f[i][j]+1;
         a[u][v]=1;
         so++;
         x[so] = v;
         y[so] = u;
        // printf("",so);
        // printf("%d %d %d\n",so,u,v);
     }
     v = j;u = i+1;
     if( check(u,v) == 1) 
     {
         f[u][v] = f[i][j]+1;
         a[u][v]=1;
         so++;
         x[so] = v;
         y[so] = u;
         // printf("%d %d %d\n",so,u,v);
        // printf("",so);
     }
     v = j;u = i-1;
     if( check(u,v) == 1) 
     {
         f[u][v] = f[i][j]+1;
         a[u][v]=1;
         so++;
         x[so] = v;
         y[so] = u;
        // printf("",so);
        // printf("%d %d %d\n",so,u,v);
     }
}
int main()
{
    //freopen("VMUNCH.in","r",stdin);
    scanf("%d %d",&n,&m);
    for(int i = 0;i<n;i++)
    {
       scanf("%s",s[i]);
       for(int j = 0;j<m;j++)
       {
           a[i][j] = 0;f[i][j]=-1;
          if(s[i][j] == 'B')
          {     x1 = j;y1=i;a[i][j]=1,f[i][j]=0,x[1]=j,y[1]=i;}
          else if(s[i][j] == 'C')
          {    x2 = j; y2= i;}
          else if(s[i][j]=='*') a[i][j] = 1;
         // printf("%d  ",a[i][j]);
       }
         // printf("\n%d %d %d %d",x1,y1,x2,y2);
       //printf("\n");
    }

    for(int i = 1;;i++)
    {
       // printf("%d %d %d\n",i,x[i],y[i]);
        if(f[y2][x2]>=0)
            break;
        else
            xuly(x[i],y[i]);
    }

    printf("%d",f[y2][x2]);
    //getch();
}

Code mẫu của ll931110

Program VMUNCH;
        Const
                input  = '';
                output = '';
        Var
                            s: array[0..101,0..101] of boolean;
               adj,head,trace: array[0..30000] of integer;
                          r,c: integer;
                 start,finish: integer;

Procedure LoadGraph;
          Var
                f: text;
              i,j: integer;
               ch: char;
          Begin
                Assign(f, input);
                        Reset(f);
                        Readln(f, r, c);

                Fillchar(s, sizeof(s), false);

                For i:= 1 to r do
                    Begin
                        For j:= 1 to c do
                                Begin
                                        Read(f, ch);

                                        Case ch of
                                                '.': s[i,j]:= true;
                                                'C': Begin
                                                        start:= c * (i - 1) + j;
                                                        s[i,j]:= true;
                                                     End;
                                                'B': Begin
                                                        finish:= c * (i - 1) + j;
                                                        s[i,j]:= true;
                                                     End;
                                        End;
                                End;
                        readln(f);
                    End;
                Close(f);
          End;

Procedure init;
          Var
                numadj,i,j: longint;
          Begin
                numadj:= 0;

                For i:= 1 to r do
                        For j:= 1 to c do
                                Begin
                                        Head[c * (i - 1) + j]:= numadj;
                                        If s[i,j] then
                                                Begin
                                                        If s[i - 1,j] then
                                                                Begin
                                                                        inc(numadj);
                                                                        adj[numadj]:= c * (i - 2) + j;
                                                                End;

                                                        If s[i,j - 1] then
                                                                Begin
                                                                        inc(numadj);
                                                                        adj[numadj]:= c * (i - 1) + (j  - 1);
                                                                End;

                                                        If s[i,j + 1] then
                                                                Begin
                                                                        inc(numadj);
                                                                        adj[numadj]:= c * (i - 1) + (j + 1);
                                                                End;

                                                        If s[i + 1,j] then
                                                                Begin
                                                                        inc(numadj);
                                                                        adj[numadj]:= c * i + j;
                                                                End;
                                                End;
                                End;

                head[r * c + 1]:= numadj;
          End;

Procedure BFS;
          Var
                         Queue: array[1..30000] of integer;
                front,rear,u,v: integer;
          Begin
                front:= 1;      rear:= 1;

                Queue[1]:= start;
                Fillchar(trace, sizeof(trace), 0);
                trace[start]:= -1;

                Repeat
                        u:= Queue[front];
                        inc(front);

                        For v:= head[u] + 1 to head[u + 1] do if trace[adj[v]] = 0 then
                                Begin
                                        inc(rear);
                                        queue[rear]:= adj[v];
                                        trace[adj[v]]:= u;
                                End;
                Until front > rear;

          End;

Procedure solve;
          Var
                  f: text;
                num: integer;
          Begin
                Assign(f, output);
                        Rewrite(f);
                        num:= 0;

                        While finish <> start do
                                Begin
                                        inc(num);
                                        finish:= trace[finish];
                                End;

                        Writeln(f, num);
                Close(f);
          End;

Begin
        LoadGraph;
        init;
        BFS;
        solve;
End.

Code mẫu của skyvn97

#include<stdio.h>
#include<queue>
#define MAX   111
using namespace std;
typedef pair<int,int> ii;
int c[MAX][MAX];
int l[MAX][MAX];
int m,n;
ii s,e;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
void init(void) {
    scanf("%d",&m);
    scanf("%d",&n);
    int i,j;
    char t[MAX];
    for (i=0;i<=m+1;i=i+1) {
        c[i][0]=2;
        c[i][n+1]=2;
    }
    for (i=0;i<=n+1;i=i+1) {
        c[0][i]=2;
        c[m+1][i]=2;
    }
    for (i=1;i<=m;i=i+1)
        for (j=1;j<=n;j=j+1) {
            c[i][j]=0;
            l[i][j]=0;
        }
    for (i=1;i<=m;i=i+1) {
        scanf("%s",t);
        for (j=1;j<=n;j=j+1)
            {
                if (t[j-1]=='*') c[i][j]=2;
                if (t[j-1]=='B') s=ii(i,j);
                if (t[j-1]=='C') e=ii(i,j);
            }
    }
}
void bfs(void) {
    queue<ii> q;
    c[s.first][s.second]=1;
    ii t;
    int i,x,y;
    q.push(s);
    while (!q.empty())
        {
            t=q.front(); q.pop();
            x=t.first;
            y=t.second;
            if (t==e)
                {
                    printf("%d",l[x][y]);
                    return;
                }
            for (i=0;i<4;i=i+1)
                if (c[x+dx[i]][y+dy[i]]==0) {
                    c[x+dx[i]][y+dy[i]]=1;
                    l[x+dx[i]][y+dy[i]]=l[x][y]+1;
                    q.push(ii(x+dx[i],y+dy[i]));
                }
        }
}
int main(void) {
    init();
    bfs();
}

Code mẫu của khuc_tuan

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

int m, n;
char a[111][111];
queue< pair<int,int> > q;
pair<int,int> f[111][111];

int main() {
    scanf("%d%d", &m, &n);
    gets(a[0]);
    for(int i=0;i<m;++i) gets(a[i]);
    for(int i=0;i<111;++i) for(int j=0;j<111;++j) f[i][j] = make_pair( 11111, 0);
    for(int i=0;i<m;++i) for(int j=0;j<n;++j) if(a[i][j]=='C') {
        q.push( make_pair( i, j));
        f[i][j] = make_pair( 0, -1);
    }
    while(!q.empty()) {
        int u = q.front().first;
        int v = q.front().second;
        q.pop();
        for(int dx=-1;dx<=1;++dx) for(int dy=-1;dy<=1;++dy) if((dx!=0) ^ (dy!=0)) {
            int x = u + dx;
            int y = v + dy;
            if(x<0 || x>=m || y<0 || y>=n) continue;
            if(a[x][y]=='*') continue;
            int t = a[x][y]=='.' ? -1 : 0;
            if(f[x][y] > make_pair( f[u][v].first+1, f[u][v].second+t)) {
                f[x][y] = make_pair(f[u][v].first+1, f[u][v].second+t);
                q.push( make_pair( x, y));
            }
        }
    }
    for(int i=0;i<m;++i) for(int j=0;j<n;++j) if(a[i][j]=='B') {
        cout << -f[i][j].second << endl;    
    }
    //system("pause");
    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.