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.

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

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.