LABUDOVI – spoj

Đề bài:

Thuật toán:

  • BFS
  • Bài này chú ý dùng phương pháp loang đồ thị để làm; chúng ta sẽ dùng 2 mảng nextx, nexty để loang ra 4 ô xung quanh của 1 ô.
  • Đầu tiên đánh dấu vị trí của 2 con thiên nga và đánh dấu tất cả các ô là nước.
  • Sau đó tiến hành loang từ con thiên nga thứ nhất. Nếu gặp con thiên nga thứ hai thì return.
    Nếu không thì tiến hành loang các ô bên cạnh là ô băng; nếu gặp ô băng thì chuyển thành ô nước, đánh dấu lại và tăng biến đếm lên 1. Tiếp tục như vậy cho tới khi gặp được con thiên nga thứ hai.

Code:

#include <bits/stdc++.h>
 
using namespace std;
 
 
#define task ""
#define fi first
#define se second
#define maxinp (int)(1500)
#define MODUL (int)(1e9+57)
#define siz(x) (int)(x.size())
#define len(x) (int)(x.length())
#define whole(x) x.begin(), x.end()
#define FOR(i, x, y) for(int i=x; i<=y; ++i)
#define FORl(i, x, y) for(int i=x; i<y; ++i)
#define FORb(i, x, y) for(int i=x; i>=y; --i)
#define FORlb(i, x, y) for(int i=x; i>y; --i)
#define MEMS(x, val) memset(x, val, sizeof(x))
#define FILEOP(x) freopen(x".inp", "r", stdin); freopen(x".out", "w", stdout);
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef queue<ii> qii;
typedef long long ll;
int nextx[4] = {-1, 0, 0, 1};
int nexty[4] = {0, -1, 1, 0};
bool Free[maxinp][maxinp];
int Time[maxinp][maxinp];
char a[maxinp][maxinp];
int m, n, res, nTime;
qii mainq, subq;
ii start[3];
int nInstruction = 0;
void Debug()
{
 
    cout << endl;
    FOR(i, 1, m)
    {
        FOR(j, 1, n)
        {
            cout << Time[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
 
 
}
 
 
void Enter()
{
	int cnt = 1;
	MEMS(Free, true);
 
 
	scanf("%d%d", &m, &n);
 
 
 
 
	FOR(i, 1, m)
	{
	    FOR(j, 1, n)
	    {
 
	        cin >> a[i][j];
 
 
            if(a[i][j] != 'X')
            {
                Time[i][j] = 0;
 
                mainq.push(ii(i, j));
 
                if(a[i][j] == 'L')
                {
                    start[cnt] = ii(i, j);
                    ++cnt;
                }
 
                Free[i][j] = false;
            }
            else Time[i][j] = 1234567890;
 
            ++nInstruction;
 
 
	    }
	}
 
}
 
//Check
bool IsValid(int _x, int _y)
{
    return(_x >= 1 && _y >= 1 && _x <= m && _y <= n && Free[_x][_y]);
}
 
void PreProcess()
{
    while(!mainq.empty())
    {
        int curx = mainq.front().first;
        int cury = mainq.front().second;
 
        ++nInstruction;
        mainq.pop();
 
        FOR(i, 0, 3)
        {
            int x = curx + nextx[i];
            int y = cury + nexty[i];
 
            if(IsValid(x, y))
            {
                if(a[x][y] == 'X')
                {
                    Free[x][y] = false;
                    mainq.push(ii(x, y));
                    Time[x][y] = min(Time[x][y], Time[curx][cury] + 1);
                }
            }
        }
 
    }
 
    //Debug();
 
 
 
}
void FloodFill1(ii st1, ii st2)
{
    mainq.push(st1);
    Free[st1.first][st1.second] = false;
    while(!mainq.empty())
    {
        int curx = mainq.front().first;
        int cury = mainq.front().second;
 
        //Time[curx][cury] = nTime;
        ++nInstruction;
 
        mainq.pop();
 
        FOR(i, 0, 3)
        {
            int x = curx + nextx[i];
            int y = cury + nexty[i];
            ii dir = ii(x, y);
 
            if(IsValid(x, y))
            {
                Free[x][y] = false;
                if(dir == st2) return;
                if(Time[x][y] <= res) mainq.push(dir);
                else subq.push(dir);
            }
        }
 
        if(mainq.empty())
        {
            ++res;
            swap(mainq, subq);
        }
 
    }
}
 
//Process
void Solve()
{
    res = 0;
    PreProcess();
    MEMS(Free, true);
    FloodFill1(start[1], start[2]);
    printf("%d", res);
 
 
    cerr << endl;
    cerr << nInstruction << endl;
 
}
 
//Main Procedure
int main()
{
    Enter();
    Solve();
    return 0;
}

QBAGENTS – spoj

Đề bài:

Thuật toán:

  • BFS

Code:

uses    math;
const   fi='';
        fo='';
        maxn=300;
        maxm=maxn*maxn;
        oo=trunc(1e9);
type    Tq      =record
                u1,u2,k :longint;
                end;
var     q       :array[1..2*maxn*maxn*10] of Tq;
        cx      :array[1..maxn,1..maxn,1..2] of boolean;
        f       :array[1..maxn,1..maxn,1..2] of longint;
        i,j,n,m,s,t     :longint;
        dau,cuoi,res    :longint;
        // danh sach
        link,head,ke    :array[1..maxm] of longint;
procedure enter;
var     u,v     :longint;
begin
        assign(input,fi);reset(input);
        readln(n,m,s,t);
        for i:=1 to m do
                begin
                        read(u,v);
                        link[i] := head[u];
                        head[u] :=i;
                        ke[i] := v;
                end;
        close(input);
end;
procedure push(x,y,z:longint);
begin
        inc(cuoi);
        q[cuoi].u1:=x;
        q[cuoi].u2:=y;
        q[cuoi].k:=z;
end;
procedure process;
var     v1,v2,u1,u2,k :longint;
begin
        dau :=1; cuoi :=0;
        push(s,t,1);
        fillchar(cx,sizeof(cx),true);
        //
        for i:=1 to n do
                for j:=1 to n do
                        for k:=1 to 2 do
                                f[i,j,k] := oo;
        f[s,t,1] := 0;
        while dau<=cuoi do
                begin
                        u1 := q[dau].u1;
                        u2 := q[dau].u2;
                        k := q[dau].k;
                        inc (dau);
                        if k=1 then
                                begin
                                        i := head[u1];
                                        while i>0 do
                                                begin
                                                        v1 := ke[i];
                                                        if cx[v1,u2,2] then
                                                          begin
                                                                f[v1,u2,2] := min(f[v1,u2,2],f[u1,u2,1]+1);
                                                                push(v1,u2,2);
                                                                cx[v1,u2,2] := false;
                                                          end;
                                                        i:= link[i];
                                                end;
                                end;
                        if k=2 then
                                begin
                                        i := head[u2];
                                        while i>0 do
                                                begin
                                                        v2 := ke[i];
                                                        if cx[u1,v2,1] then
                                                          begin
                                                                f[u1,v2,1] := min(f[u1,u2,2]+1,f[u1,v2,1]);
                                                                push(u1,v2,1);
                                                                cx[u1,v2,1] := false;
                                                          end;
                                                        i:= link[i];
                                                end;
                                end;
                end;
        res := oo;
        for i:=1 to n do
                res := min(res,f[i,i,1]);
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        if res=oo then write(-1) else write(res div 2);
        close(output);
end;
begin
        enter;
        process;
        print;
end.

BCISLAND – ptit

Đề bài:


Thuật toán:


- Bài này chia ra làm các bước như sau:
+ B1: Tìm độ cao lớn nhất so với mặt nước biển. (Hmax)
+ B2: Với độ cao tăng thêm: extra = 1-&gt;Hmax ta sẽ loang bắt đầu từ các cạnh là biển loang vào những nới có độ (độ cao &lt;= extra).
VD: có bản đồ:
5 5 5 5 7
4 1 1 1 4
4 1 2 1 3
7 1 0 0 4
7 3 4 4 4
với extra=1 ta thu được check[][]:
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

+B3: Đếm số thành phần liên thông tại check[][] với các check[][]==0 bằng DFS;
Số thành phần liên thông &gt; 1 thì tại độ cao extra đó đảo bị chia cắt;
VD: ở bản đồ trên tại extra = 3 ta có check[][]:
0 0 0 0 0
0 1 1 1 0
0 1 0 1 1
0 1 1 1 0
0 1 0 0 0

Code:


#include <iostream>
using namespace std;
 
int n, m;
int seawater[102][102];
int Hmax=0;
void read ()
{
	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=m; j++)
		{
			cin>>seawater[i][j];
			if (seawater[i][j]>Hmax) Hmax=seawater[i][j];
		}
	}
}
 
int check[102][102];
int check_connect[102][102];
void init ()
{
	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=m; j++)
		{
			check[i][j]=0;
			check_connect[i][j]=0;
		}
	}
}
 
int extra;
int x_ar[]={+1, +0, -1, +0};
int y_ar[]={+0, -1, +0, +1};
void loang (int i, int j)
{
	check[i][j]=1;
	for (int k=0; k<4; k++)
	{
		int X=j+x_ar[k];
		int Y=i+y_ar[k];
		if (X>=1 && X<=m && Y>=1 && Y<=n)
		{
			if (check[Y][X]==0 && seawater[Y][X]<=extra) loang (Y, X);
		}
	}
}
 
void DFS (int i, int j)
{
	check_connect[i][j]=1;
	for (int k=0; k<4; k++)
	{
		int X=j+x_ar[k];
		int Y=i+y_ar[k];
		if (X>=1 && X<=m && Y>=1 && Y<=n)
		{
			if (check_connect[Y][X]==0 && check[Y][X]==check[i][j]) DFS (Y, X);
		}
	}
}
 
int main ()
{
	int t=0;
	while (1)
	{
		cin>>n>>m;
		if (n==0 && m==0) break;
		t++;
		read ();
		int kt=0;
		for (int k=0; k<=Hmax; k++)
		{
			extra=k;
			init ();
			for (int i=1; i<=n; i++)
			{
				for (int j=1; j<=m; j++)
				{
					if ((i==1 || i==n || j==1 || j==m) && seawater[i][j]<=k && check[i][j]==0) loang (i, j);
				}
			}
			//dem lien thong?
			int count_connect=0;
			for (int i=1; i<=n; i++)
			{
				for (int j=1; j<=m; j++)
				{
					if (check_connect[i][j]==0 && check[i][j]==0)
					{
						count_connect++;
						DFS (i, j);
					}
				}
			}
			if (count_connect>1)
			{
				kt=1;
				break;
			}
		}
		if (kt==1) cout<<"Case "<<t<<": Island splits when ocean rises "<<extra<<" feet."<<endl;
		else cout<<"Case "<<t<<": Island never splits."<<endl;
	}
	return 0;
}

STABLE – spoj

Đề bài:

Thuật toán:

  • BFS từ đỉnh S
  • Gọi bac[i] là đồ dài đường đi ngắn nhất từ s đến i
    • bac[i] = bac[j] + 1
    • với i kề j và j duyệt BFS trước i
  • ok[i] = 1 nếu i ổn định, ok[i] = 0 nếu i không ổn định.
  • Hãy tham khảo code để biết cách kiểm tra xem i có ổn định không

Code:

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define double db
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
const int MAXN = 1E4+3;
const int oo = 1e9+3;
 
int n, m, s, u, v, res, bac[MAXN],adj[MAXN][MAXN];
bool ok[MAXN];
queue<int> q;
vector<int> a[MAXN];
 
int main() {
    	#ifndef ONLINE_JUDGE
    	freopen("test.inp", "r", stdin);
    	freopen("test.out", "w", stdout);
    	#endif
    cin >> n >> m >> s;
    FOR(i,1,m) {
        cin >> u >> v;
        if (!adj[u][v])
            a[u].push_back(v);
        adj[u][v] = 1;
    }
    q.push(s); bac[s] = 1;
    while (!q.empty()) {
        u = q.front();
        q.pop();
        for(int i=0; i<a[u].size(); i++)
        {
            v = a[u][i];
            if (!bac[v])
            {
                if (ok[u]) ok[v] = 1;
                bac[v] = bac[u] + 1;
                q.push(v);
            }
            else
            if (bac[v] == bac[u] + 1) ok[v] = 1;
        }
    }
    FOR(i,1,n) if (ok[i]) res++;
    cout << res;
	return 0;
}
const
  fi='stable.inp';
  fo='stable.out';
  maxn=10000;
  maxm=50000;
var
  link,head,ke : array[1..maxm] of longint;
  i,j,n,m,st,ans,s,dau,cuoi,u,v : longint;
  q,bac : array[1..maxn] of longint;
  ok : array[1..maxn] of boolean;
  a : array[1..maxn,1..maxn] of boolean;
procedure push(x : longint);
  begin
    inc(cuoi);
    q[cuoi] := x;
  end;
procedure add(i,u,v : longint);
  begin
    link[i] := head[u];
    head[u] := i;
    ke[i] := v;
  end;
begin
//  assign(input,fi);reset(input);
//  assign(output,fo);rewrite(output);
  read(n,m,s);
  for i := 1 to m do
    begin
      read(u,v);
      if a[u,v] = false then
      add(i,u,v);
      a[u,v] := true;
    end;
  dau := 1; cuoi := 0;
  push(s);
  bac[s] := 1;
  while (dau <= cuoi) do
    begin
      u := q[dau];
      inc(dau);
      i := head[u];
      while i <> 0 do
        begin
          v := ke[i];
          if bac[v] = 0 then
            begin
              if ok[u] then ok[v] := true;
              bac[v] := bac[u] + 1;
              push(v);
            end
            else
          if bac[v] = bac[u] + 1 then
            begin
              ok[v] := true;
            end;
          i := link[i];
        end;
    end;
  for i := 1 to n do
    if ok[i] then inc(ans);
  writeln(ans);
//  close(input);close(output);
end.

QBBISHOP – spoj

Đề bài: [xem đề bài]

covua-yeulaptrinh.pw

Thuật toán:

  • BFS từ ô (s.x,s.y)
  • Mỗi lần BFS lấy ra ô (u,v) đi theo 4 đường chéo có dạng (u-x,v-x) , (u-x,v+x) , (u+x,v-x) , (u+x,v+x).
  • Đừng quên là không thể đi đến ô đang có cờ.

Code: [xem code]

const   fi='';
        fo='';
        maxn=200;
        dx:array[1..4] of integer =(1,-1,1,-1);
        dy:array[1..4] of integer =(1,1,-1,-1);
type    point=record
                x,y:integer;
                end;
var     free:array[0..maxn+1,0..maxn+1] of boolean;
        bac:array[0..maxn+1,0..maxn+1] of integer;
        q:array[1..maxn*maxn] of point;
        n,m,i,j:integer;
        s,f:point;
        dau,cuoi,res:longint;
procedure nhap;
var     x,y:integer;
begin
    assign(input,fi);reset(input);
    readln(n,m,s.x,s.y,f.x,f.y);
    fillchar(free,sizeof(free),false);
    for i:=1 to n do
        for j:=1 to n do free[i,j]:=true;
    for i:=1 to m do
        begin
            readln(x,y);
            free[x,y]:=false;
        end;
end;
procedure init;
begin
 
end;
procedure push(x,y:integer);
begin
    inc(cuoi);
    q[cuoi].x:=x;
    q[cuoi].y:=y;
end;
procedure bfs;
var     u,v:point;
begin
    dau:=1;cuoi:=1;
    q[1].x:=s.x;q[1].y:=s.y;
    while dau<=cuoi do
        begin
            u:=q[dau]; inc(dau);
            for i:=1 to 4 do
                for j:=1 to n do
                        begin
                            v.x:=dx[i]*j+u.x;
                            v.y:=dy[i]*j+u.y;
                            if (v.x=f.x) and (v.y=f.y) then
                                begin
                                        res:=bac[u.x,u.y]+1;
                                        exit;
                                end;
                            if (v.x>=1) and (v.y>=1) and (v.x<=n) and (v.y<=n) and (free[v.x,v.y])  then
                                begin
                                   bac[v.x,v.y]:=bac[u.x,u.y] +1;
                                   free[v.x,v.y]:=false;
                                   push(v.x,v.y);
                                end else break;
                        end;
        end;
    res:=-1;exit;
end;
procedure xuly;
begin
    if (s.x+s.y) mod 2<>(f.x+f.y) mod 2 then begin res:=-1; exit; end;
    bfs;
 
end;
procedure inkq;
begin
    assign(output,fo);rewrite(Output);
 
    writeln(res);
 
    close(output);
end;
begin
    nhap;
    init;
    xuly;
    inkq;
end.

ROBOCON – vn.spoj.com

Đề bài: http://vn.spoj.com/problems/ROBOCON/

Thuật toán:

  • Bạn loang con robot 1 trong khi loang robot 1 bạn cũng đồng thời loang robot 2. Ta phải suy luận ra một số trường hợp để mà dừng loang
  • Bạn có thể đọc code của mình để hiểu thêm. Mình viết rất dễ hiểu, bạn đọc có thể hiểu ngay

Code:

const
  fi='';
  fo='';
  maxn=501;
  maxq=20*maxn*maxn;
  oo=trunc(1e9);
type
  point = record
    x,y,d : longint;
  end;
var
  dau1,cuoi1,dau2,cuoi2,i,j,n,m : longint;
  a : array[0..maxn,0..maxn] of boolean;
  q1,q2 : array[1..maxq] of point;
  d1,d2 : array[1..maxn,1..maxn] of longint;
  nowd,res : longint;
  kt : boolean;
 
procedure enter;
var u,v : longint;
begin
  assign(input,fi);reset(input);
  fillchar(a , sizeof(a) , false);
  readln(n,m);
  for i:=1 to n do for j:=1 to n do a[i,j] := true;
  for i:=1 to m do
    begin
      read(u,v);
      a[u,v] := false;
    end;
end;
procedure push1(x,y,z : longint);
begin
  inc(cuoi1);
  q1[cuoi1].x := x;
  q1[cuoi1].y := y;
  q1[cuoi1].d := z;
  d1[x,y] := z;
  if d2[x,y]=z then
    begin
      res := z;
      kt:=true;
      exit;
    end;
end;
procedure push2(x,y,z : longint);
begin
  inc(cuoi2);
  q2[cuoi2].x := x;
  q2[cuoi2].y := y;
  q2[cuoi2].d := z;
  d2[x,y] := z;
end;
procedure bfs2(dd : longint);
var u : point;
    i,j : longint;
begin
  while dau2<=cuoi2 do
    begin
      u := q2[dau2]; inc(dau2);
      if u.d>dd then begin dec(dau2); exit; end;
      i:=u.x;j:=u.y;
      if a[i,j-1] and (d2[i,j-1]<>dd+1) then push2(i,j-1,dd+1);
      if a[i+1,j] and (d2[i+1,j]<>dd+1) then push2(i+1,j,dd+1);
      if a[i+1,j-1] and (d2[i+1,j-1]<>dd+1) then push2(i+1,j-1,dd+1);
    end;
end;
procedure bfs1;
var u : point;
    i,j : longint;
begin
  fillchar(d1,sizeof(d1),255);
  fillchar(d2,sizeof(d2),255);
  kt := false;
  dau1 :=1; cuoi1 := 0;
  dau2 := 1; cuoi2 := 0;
  push1(1,1,0); push2(1,n,0);
  nowd := 0;
  while dau1<=cuoi1 do
    begin
      if kt then break;
      u := q1[dau1]; inc(dau1);
      if u.d=nowd then
        begin
          bfs2(nowd);
          inc(nowd);
        end;
      i := u.x ; j:=u.y;
      if a[i+1,j] and (d1[i+1,j]<>u.d+1) then push1(i+1,j,u.d+1);
      if a[i,j+1] and (d1[i,j+1]<>u.d+1) then push1(i,j+1,u.d+1);
      if a[i+1,j+1] and (d1[i+1,j+1]<>u.d+1) then push1(i+1,j+1,u.d+1);
    end;
end;
procedure process;
begin
  res := oo;
  bfs1;
end;
procedure print;
begin
  assign(output,fo);rewrite(output);
  writeln(res);
  close(output);
end;
begin
  enter;
  process;
  print;
end.