Hướng dẫn giải của Laser Phones
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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); maxn=110; var n,m,re:longint; a:array[1..maxn,1..maxn] of char; d:array[1..maxn,1..maxn,1..4] of byte; s:array[0..1,0..1] of longint; q:array[1..1000000,0..3] of longint; procedure rf; var i,j,k:longint; begin readln(n,m); k:=-1; 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 inc(k); s[k,0]:=i; s[k,1]:=j; end; end; readln; end; end; function check(x,y:longint):Boolean; begin check:=(x>0) and (y>0) and (x<=m) and (y<=n) and (a[x,y]<>'*'); end; procedure pr; var i,j,k,x,y,dir,x1,y1,num,t:longint; begin fillchar(d,sizeof(d),0); x:=s[0,0]; y:=s[0,1]; d[x,y,1]:=1; num:=4; for j:=1 to 4 do begin q[j,0]:=x; q[j,1]:=y; q[j,2]:=j; q[j,3]:=0; d[x,y,j]:=1; end; i:=1; re:=100000; repeat x:=q[i,0]; y:=q[i,1]; dir:=q[i,2]; if (x=s[1,0]) and (y=s[1,1]) and (q[i,3]<re) then re:=q[i,3]; for j:=1 to 4 do begin x1:=x+dx[j]; y1:=y+dy[j]; if not check(x1,y1) then continue; if d[x1,y1,j]=0 then begin inc(num); q[num,0]:=x1; q[num,1]:=y1; q[num,2]:=j; q[num,3]:=q[i,3]; if j<>dir then inc(q[num,3]); d[x1,y1,j]:=q[num,3]; end else begin t:=q[i,3]; if j<>dir then inc(t); if t<d[x1,y1,j] then begin inc(num); q[num,0]:=x1; q[num,1]:=y1; q[num,2]:=j; q[num,3]:=t; d[x1,y1,j]:=t; end; end; end; inc(i); until i>num; end; procedure wf; begin write(re); 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 <iostream> #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; typedef long long LL; #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(); i != _e; ++i) #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 105 char a[N][N]; //field map bool vst[N][N]; int h, w, d[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; //h: so cot, w: so hang ii p[2]; void enter() { int k = 0; scanf("%d%d",&h,&w); rep(i,w) scanf("%s", a[i]); rep(i,w) rep(j,h) if(a[i][j] == 'C') p[k++] = ii(i,j); } void solve() { queue<ii> qu; qu.push(p[0]); vst[p[0].fi][p[0].se] = 1; for(int cnt = -1; !qu.empty(); ++cnt) { rep(K,qu.size()) { if(qu.front() == p[1]) { printf("%d\n", cnt); return; } int x = qu.front().fi, y = qu.front().se; qu.pop(); rep(k,4) for(int i=x,j=y; i>=0&&i<w&&j>=0&&j<h&&a[i][j]!='*'; i+=d[k][0],j+=d[k][1]) { if(vst[i][j]) continue; qu.push(ii(i,j)); vst[i][j] = 1; } } } } int main() { #ifndef ONLINE_JUDGE freopen( "input.txt", "r", stdin ); //freopen( "output.txt", "w", stdout ); #endif enter(); solve(); return 0; }
Code mẫu của ladpro98
program mlaser; uses math; type e=record x,y:longint; end; const maxn=110; fi=''; dx:array[1..4] of longint = (-1,0,0,1); dy:array[1..4] of longint = (0,1,-1,0); var a:array[1..maxn,1..maxn] of char; check:array[1..maxn,1..maxn] of boolean; p:array[1..maxn,1..maxn] of longint; s:array[1..2] of e; q:array[1..maxn*maxn] of e; m,n,d:longint; procedure input; var inp:text; i,j:longint; begin assign(inp,fi);reset(inp); readln(inp,n,m); for i:=1 to m do begin for j:=1 to n do begin read(inp,a[i,j]); if a[i,j]='C' then begin inc(d); s[d].x:=i; s[d].y:=j; end; end; readln(inp); end; close(inp); end; procedure bfs; var l,r,i,x,y:longint; u:e; begin l:=1;r:=1; q[1]:=s[1]; check[s[1].x,s[1].y]:=true; p[s[1].x,s[1].y]:=-1; while l<=r do begin u:=q[l];inc(l); for i:=1 to 4 do begin x:=u.x;y:=u.y; while true do begin x:=x+dx[i]; y:=y+dy[i]; if (1<=x) and (x<=m) and (1<=y) and (y<=n) and (a[x,y]<>'*') then begin if not check[x,y] then begin inc(r); q[r].x:=x; q[r].y:=y; check[x,y]:=true; p[x,y]:=p[u.x,u.y]+1; if (x=s[2].x) and (y=s[2].y) then exit; end; end else break; end; end; end; end; begin input; bfs; write(p[s[2].x,s[2].y]); end.
Code mẫu của RR
{$R+,Q+} uses math; const FINP=''; FOUT=''; MAXN=101; di:array[1..4] of longint=(-1,1,0,0); dj:array[1..4] of longint=(0,0,-1,1); dh:array[1..4] of longint=(0,0,1,1); oo=1000001; var f1,f2:text; m,n,hsize,startu,startv,targetu,targetv:longint; a:array[1..MAXN,1..MAXN] of char; hpos,d:array[1..MAXN,1..MAXN,0..1] of longint; hu,hv,ht:array[1..MAXN*MAXN*2] of longint; procedure openF; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); end; procedure closeF; begin close(f1); close(f2); end; procedure swap(var a,b:longint); var temp:longint; begin temp:=a; a:=b; b:=temp; end; procedure inp; var i,j:longint; begin readln(f1,n,m); for i:=1 to m do begin for j:=1 to n do begin read(f1,a[i,j]); if a[i,j]='C' then if startu=0 then begin startu:=i; startv:=j; end else begin targetu:=i; targetv:=j; end; end; readln(f1); end; end; procedure downHeap(i:longint); var j:longint; begin j:=i<<1; while (j<=hsize) do begin if (j<hsize) and (d[hu[j+1],hv[j+1],ht[j+1]]<d[hu[j],hv[j],ht[j]]) then inc(j); if (d[hu[j],hv[j],ht[j]]<d[hu[i],hv[i],ht[i]]) then begin swap(hpos[hu[i],hv[i],ht[i]],hpos[hu[j],hv[j],ht[j]]); swap(hu[i],hu[j]); swap(hv[i],hv[j]); swap(ht[i],ht[j]); end; i:=j; j:=i<<1; end; end; procedure upHeap(i:longint); var j:longint; begin j:=i>>1; while (i>1) and (d[hu[i],hv[i],ht[i]]<d[hu[j],hv[j],ht[j]]) do begin swap(hpos[hu[i],hv[i],ht[i]],hpos[hu[j],hv[j],ht[j]]); swap(hu[i],hu[j]); swap(hv[i],hv[j]); swap(ht[i],ht[j]); i:=j; j:=i>>1; end; end; procedure push(u,v,t:longint); begin inc(hsize); hu[hsize]:=u; hv[hsize]:=v; ht[hsize]:=t; hpos[u,v,t]:=hsize; upHeap(hsize); end; procedure pop(var u,v,t:longint); begin u:=hu[1]; v:=hv[1]; t:=ht[1]; hpos[u,v,t]:=0; swap(hu[1],hu[hsize]); swap(hv[1],hv[hsize]); swap(ht[1],ht[hsize]); hpos[hu[1],hv[1],ht[1]]:=1; dec(hsize); downHeap(1); end; procedure solve; var huong,u,v,t,uu,vv,tt:longint; begin for u:=1 to m do for v:=1 to n do for t:=0 to 1 do d[u,v,t]:=oo; u:=startu; v:=startv; hsize:=0; d[u,v,0]:=0; d[u,v,1]:=0; push(u,v,0); push(u,v,1); while hsize>0 do begin pop(u,v,t); if (u=targetu) and (v=targetv) then begin writeln(f2,d[u,v,t]); exit; end; for huong:=1 to 4 do begin uu:=u+di[huong]; vv:=v+dj[huong]; tt:=dh[huong]; if (uu>0) and (vv>0) and (uu<=m) and (vv<=n) and (a[uu,vv]<>'*') then begin if (t=tt) and (d[uu,vv,tt]>d[u,v,t]) then begin d[uu,vv,tt]:=d[u,v,t]; if hpos[uu,vv,tt]=0 then push(uu,vv,tt) else upHeap(hpos[uu,vv,tt]); end; if (t<>tt) and (d[uu,vv,tt]>d[u,v,t]+1) then begin d[uu,vv,tt]:=d[u,v,t]+1; if hpos[uu,vv,tt]=0 then push(uu,vv,tt) else upHeap(hpos[uu,vv,tt]); end; end; end; end; end; begin openF; inp; solve; closeF; end.
Code mẫu của hieult
#include <cstdio> //#include <conio.h> int cols,rows; char map[128][128]; int cowrow1,cowcol1,cowrow2,cowcol2; void read_input() { int row,col,cows = 0; scanf("%d %d",&cols,&rows); for(row = 0;row<rows;row++) { scanf("%s",map[row]); for(col = 0;col<cols;col++) if(map[row][col] =='C') { if(cows==0) {cowrow1 = row;cowcol1 = col;} if(cows==1){ cowrow2 = row; cowcol2 = col;} cows++; } } } int calc_steps() { int DR[] = {-1,0,0,1}; int DC[] = {0,-1,1,0}; int steps[128][128]; int queue[128*128]; int readptr,writeptr; int r,c,d,rr,cc; map[cowrow2][cowcol2]='.'; map[cowrow1][cowcol1]='+'; steps[cowrow1][cowcol1] = 1; queue[0] = 128*cowrow1+cowcol1; readptr = 0; writeptr = 1; while(steps[cowrow2][cowcol2] ==0) { r = queue[readptr]/128; c = queue[readptr++]%128; for(d=0;d<4;d++) { rr = r; cc = c; while(true) { rr+=DR[d];cc+=DC[d]; if((rr<0)||(rr>rows)||(cc<0)||(cc>cols)||map[rr][cc]=='*') break; if(map[rr][cc]!='.') continue; map[rr][cc]='+'; steps[rr][cc] = steps[r][c] +1; queue[writeptr++] = 128*rr+cc; } } } return steps[cowrow2][cowcol2] - 2; } int main() { //freopen("MLASERP2.inp","r",stdin); read_input(); printf("%d\n",calc_steps()); //getch(); }
Code mẫu của ll931110
Program MLASERP; Type rec = record x: integer; y: integer; end; Const input = ''; output = ''; Var a: array[0..101,0..101] of boolean; d: array[1..100,1..100] of longint; queue: array[1..20000] of rec; dx,dy: array[1..4] of longint; h,w,sx,sy,fx,fy: longint; front,rear: longint; check: boolean; num: longint; Procedure init; Var f: text; i,j: longint; count: longint; ch: char; Begin Assign(f, input); Reset(f); Fillchar(a, sizeof(a), false); Readln(f, w, h); count:= 0; For i:= 1 to h do Begin For j:= 1 to w do Begin Read(f, ch); If ch = '.' then a[i,j]:= true else if ch = 'C' then Begin inc(count); if count = 1 then Begin sx:= i; sy:= j; End; If count = 2 then Begin fx:= i; fy:= j; End; a[i,j]:= true; End; End; Readln(f); End; Close(f); End; Procedure gens; Begin dx[1]:= -1; dx[2]:= 0; dx[3]:= 1; dx[4]:= 0; dy[1]:= 0; dy[2]:= 1; dy[3]:= 0; dy[4]:= -1; End; Procedure BFS; Var rearc: longint; u,v,k,m,n,i: longint; Begin rearc:= rear; For i:= front to rearc do Begin u:= queue[i].x; v:= queue[i].y; For k:= 1 to 4 do Begin m:= u + dx[k]; n:= v + dy[k]; While a[m,n] do Begin If d[m,n] = -1 then Begin d[m,n]:= num; inc(rear); queue[rear].x:= m; queue[rear].y:= n; If (m = fx) and (n = fy) then Begin check:= false; exit; End; End; m:= m + dx[k]; n:= n + dy[k]; End; End; End; front:= rearc + 1; End; Procedure solve; Var f: text; i,j: longint; Begin For i:= 1 to h do For j:= 1 to w do d[i,j]:= -1; d[sx,sy]:= 0; check:= true; front:= 1; rear:= 1; queue[1].x:= sx; queue[1].y:= sy; num:= 0; While check do Begin BFS; inc(num); End; Assign(f, output); Rewrite(f); Writeln(f, d[fx,fy]); Close(f); End; Begin init; gens; solve; End.
Code mẫu của khuc_tuan
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws Exception { BufferedReader kb = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(kb.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); char[][] a = new char[m][]; for (int i = 0; i < m; ++i) a[i] = kb.readLine().toCharArray(); int[] dx = new int[] { -1, 0, 1, 0 }; int[] dy = new int[] { 0, -1, 0, 1 }; Queue<int[]> q = new LinkedList<int[]>(); int[][][] F = new int[m][n][4]; int inf = 1000000000; for (int[][] a2 : F) for (int[] a1 : a2) Arrays.fill(a1, inf); tt: for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (a[i][j] == 'C') { for (int k = 0; k < 4; ++k) { q.add(new int[] { i, j, k }); F[i][j][k] = 0; } break tt; } while (!q.isEmpty()) { int[] fr = q.remove(); int u = fr[0]; int v = fr[1]; int h = fr[2]; { int x = u + dx[h]; int y = v + dy[h]; if (x >= 0 && x < m && y >= 0 && y < n && a[x][y] != '*' && F[x][y][h] > F[u][v][h]) { F[x][y][h] = F[u][v][h]; q.add(new int[] { x, y, h }); } } for (int k = 0; k < 4; ++k) { if (F[u][v][k] > F[u][v][h] + 1) { F[u][v][k] = F[u][v][h] + 1; q.add(new int[] { u, v, k }); } } } t2: for (int i = m - 1; i >= 0; --i) for (int j = n - 1; j >= 0; --j) if (a[i][j] == 'C') { int best = inf; for (int k = 0; k < 4; ++k) best = Math.min(best, F[i][j][k]); System.out.println(best); break t2; } } }
Bình luận