Từ 1 tới 3 trên tổng số 3 kết quả

Đề tài: Đếm tàu

  1. #1
    Ngày gia nhập
    03 2008
    Nơi ở
    Nhà tù
    Bài viết
    37

    Red face Đếm tàu

    Bài tâp:Đếm tàu
    Một tệp văn bản có tên fn có ghi hồ sơ một vùng biển chữ nhật chiều ngang 250 ký tự, chiều dọc 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ụ:
    111100111
    000000111
    110000000
    110011001
    Hình trên có 5 tàu

    Mình chỉ biết đếm các con tàu có chiều rộng là 1 thôi (1111),còn con tàu lớn hơn thì không biết cách làm.Các bạn có thể gợi ý cho mình cách làm bài này được không ?

  2. #2
    Ngày gia nhập
    02 2008
    Nơi ở
    Việt Nam
    Bài viết
    577

    Bạn có thể đến các giá trị 1 mà bên trái và bên trên nó là 0 hoặc không có gì, đấy là với đk các vùng tàu của bạn là hình chữ nhật.

  3. #3
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Thử cái này xem em, hình chữ nhật thì em thêm row và col sữa cái size lại tí là ok, viết hơi vội, có gì sai thì tìm giúp anh nhé T_T. Cái ship_segment để tìm tàu có diện tích lớn nhất, nhưng đề bài không yêu cầu, em bỏ cái đó đi cũng được ! Cái này C++, C thì bỏ vector đi thay bằng mãng 2 chiều, nhưng ý tưởng là breath first search thôi chẳng có gì hết, em dựa vào đó sữa theo yêu cầu C của em.
    C++ Code:
    1. #include <iostream>
    2. #include <vector>
    3. #include <cstdlib>
    4.  
    5. using namespace std;
    6.  
    7. const int MAX_SIZE = 7;
    8.  
    9. vector< vector< int > > W( MAX_SIZE, vector< int >( MAX_SIZE, 0 ) );
    10.  
    11. void initialize_maze()
    12. {
    13.     for( int i = 0, i1 = W.size(); i < i1; ++i )
    14.     {
    15.         for( int j = 0, j1 = W[ i ].size(); j < j1; ++j )
    16.         {
    17.             W[ i ][ j ] = rand() % 2;
    18.         }
    19.     }
    20. }
    21.  
    22. void find_ship( int dx, int dy , int& ship_segment )
    23. {
    24.     W[ dx ][ dy ] = 0;
    25.     // increase the segment of ship
    26.     ++ship_segment;
    27.  
    28.     if( dx + 1 < MAX_SIZE && W[ dx + 1 ][ dy ] == 1 )
    29.         find_ship( dx + 1, dy, ship_segment );
    30.     if( dx - 1 >= 0 && W[ dx - 1 ][ dy ] == 1 )
    31.         find_ship( dx - 1, dy, ship_segment );
    32.     if( dy + 1 < MAX_SIZE && W[ dx ][ dy + 1 ] == 1 )
    33.         find_ship( dx, dy + 1, ship_segment );
    34.     if( dy - 1 >= 0 && W[ dx ][ dy - 1 ] == 1 )
    35.         find_ship( dx, dy - 1, ship_segment );
    36.  
    37. }
    38.  
    39. void count_ship( int& number_ship, int& biggest_ship )
    40. {
    41.     int ship_segments = 0;
    42.     for( int dx = 0; dx < MAX_SIZE; ++dx )
    43.     {
    44.         for( int dy = 0; dy < MAX_SIZE; ++dy )
    45.         {
    46.             if( W[ dx ][ dy ] == 1 )
    47.             {
    48.                 ship_segments = 0;
    49.                 ++number_ship;
    50.                 find_ship( dx, dy, ship_segments );
    51.                 if( ship_segments > biggest_ship )
    52.                     biggest_ship = ship_segments;
    53.             }
    54.         }
    55.     }
    56. }
    57.  
    58. void print_maze()
    59. {
    60.     for( int i = 0, i1 = W.size(); i < i1; ++i )
    61.     {
    62.         for( int j = 0, j1 = W[ i ].size(); j < j1; ++j )
    63.         {
    64.             cout << " " << W[ i ][ j ];
    65.         }
    66.         cout << endl;
    67.     }
    68. }
    69.  
    70. int main()
    71. {
    72.     initialize_maze();
    73.     print_maze();
    74.  
    75.     int ships = 0;
    76.     int the_biggest_ship = 0;
    77.     count_ship( ships, the_biggest_ship );
    78.  
    79.     cout << "Number ships = " << ships << ", and the biggest ship segments = " << the_biggest_ship << endl;
    80.  
    81.     return 0;
    82. }

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn