Đếm tàu

Đếm tàu

1	1	1	1	0	0	1	1	1
0	0	0	0	0	0	1	1	1
1	1	0	0	0	0	0	0	0
1	1	0	0	1	1	0	0	1
5 tàu

               Một tệp văn bản có tên fn có ghi sơ đồ một vùng biển hình chữ nhật chiều ngang 250 kí tự, chiều dọc (số dòng) không hạn chế. Trên biển có các con tàu hình chữ nhật chứa các kí tự 1, vùng nước được biểu thị qua các kí tự 0. Biết rằng các con tàu không dính nhau. Hãy đếm số lượng tàu.

 Ví dụ, hình bên có 5 tàu.

Thuật toán

Vì các tàu không dính nhau nên ta phân biệt các tàu qua mũi tàu, tức là góc A - góc Tây-Bắc của tàu. Ta có,

số lượng tàu = số lượng mũi tàu

Mũi tàu là điểm nhận giá trị 1 và nếu bước một bước sang trái hoặc lên trên sẽ lên bờ hoặc rơi xuống biển.

Sau khi mở tệp ta đọc và xử lí từng dòng văn bản y và so sánh nó với dòng x đã xử lí trước đó. Nếu y là dòng đầu tiên, tức là dòng nằm sát bờ Bắc, ta khởi trị cho x với 250 ks tự 0 tức là ta loại trừ trường hợp bước lên bờ Bắc. Khi xử lí y, ta chú ý tách riêng trường hợp tàu nằm sát bờ Tây, tức là xét riêng y[1]. Sau mỗi lần xử lí dòng y ta copy dòng y sang x và luôn giữ cho x có chiều dài tối đa 250 kí tự như yêu cầu của đầu bài.

A	0	0	0	0	0	B
0	1	1	1	1	1
0	1	1	1	1	1
D	0	0	0	0	0	C
Con tàu ABCD

(*  Pascal  *)

program Ships;

{$B-}

uses crt;

const MN = 250;

boong = '1'; nuoc = '0';

Function Dem(fn: string): integer;

var

      f: text; d,i: integer;

      x,y: string;{x:dong tren, y:dong duoi }

begin

Dem := 0; assign(f,fn);

{$I-} reset(f); {$I+}

   if IORESULT <> 0 then exit;

x := nuoc;

         for i := 1 to 8 do x:= x+x; {x = ’00...0’}

d := 0;

while NOT EOF(f) do

begin

readln(f,y);

if (y[1]=boong)AND(x[1]=nuoc) then d:=d+1;

for i:=2 to length(y) do

               if (y[i]= boong) AND (y[i-1]= nuoc)

                  AND (x[i]= nuoc) then d:=d+1;

  x := y;

end;

Dem := d;

end;

BEGIN

n:= Dem('TAU.INP');

         if n=0 then

            write('Khong mo duoc tep/khong co tau')

else write('Tong so tau: ',n);

   readln;

END.

// C#

using System;

using System.Collections.Generic;

using System.Text;

using System.IO;

namespace SangTao1

{

    class Ships

    {

        static public string fn = "Tau.inp";

        static public string gn = "Tau.out";

        static public char boong = '1';

        static public char nuoc = '0';

        static void Main(string[] args)

        {

            Save(Count());

            Test();

            Console.WriteLine("\n Fini ");

            Console.ReadLine();

        }

        static public int Count()// dem tau

        {

            StreamReader f = File.OpenText(fn);

            string x = new string(nuoc,251);

            string y;

            string empty = "";

            int d = 0;           

            while ((y=(f.ReadLine()).Trim())

                                   != empty)               

            {               

                d += Scan(x, y); x = y;               

            }

            f.Close();  return d;

      }

           // Sánh dòng tren x với dòng dưới y

      static public int Scan(string x, string y)

      {

          int d = 0;

          if ((y[0]==boong)&&(x[0]==nuoc)) ++d;

          for (int i = 1; i < y.Length; ++i)

             if ((y[i]==boong)&&(y[i-1]==nuoc)

                    && (x[i]==nuoc)) ++d;

            return d;

      }

      static public void Save(int d) // ghi file

      { File.WriteAllText(gn, d.ToString()); }

      static public void Test()

      {

         Console.WriteLine("\n" +

                   File.ReadAllText(fn) + "\n");

         Console.WriteLine("\n" +

                   File.ReadAllText(gn) + "\n");

        }

    } // Ships

} // SangTao1