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