Biển và Đảo ! Giải thuật và cách triển khai trong C++

[rox_rook]

Biển là 1 hình vuông cấp NxN trong đó mỗi đảo là 1 dấu *, nước là 1 dấu cách. Với mỗi biển thì biết số các nhóm đảo và số đảo trong mỗi nhóm ở trên mỗi hàng và trên mỗi cột của biển đó.
VD

Thì có các dữ kiện về dòng là
1 2
3 1
1 1 1
5
2 1 1
1
Có nghĩa
- Dòng 1 có 2 nhóm đảo, nhóm 1 có 1 đảo, nhóm 2 có 2 đảo
- Dòng 2 có 2 nhóm đảo, nhóm 1 có 3 đảo, nhóm 2 có 1 đảo
- Dòng 3 có 3 nhóm đảo, nhóm 1 có 1 đảo, nhóm 2 có 1 đảo, nhóm 3 có 1 đảo
- ……
Các dữ kiện về cột là (với ý nghĩa tương tự)
1 1 1
1 2
4
2 3
2
1 2

Yêu cầu: từ các thông tin về hạn chế dòng, cột hãy xây dựng lại bản đồ

INPUT : DAO.INP
- Dòng đầu ghi số N
- N dòng tiếp ghi lần lượt các dữ kiện về dòng
- N dòng tiếp nữa ghi lần lượt các dữ kiện về cột
OUTPUT: DAO.OUT : ghi ra bản đồ đảo xây dựng đc

Bài này thì mình cũng đang làm.hì hì ! Các bạn cùng làm nhé !

[kidkid]

Hiện tại rox_rock có ý tưởng gì chưa nhỉ ?

[rox_rook]

hì hì ! Cuối cùng có người vào làm chung roài ^^ ! Hiên đang ngày trong tuần nên mình chưa có rảnh, có gì cuối tuần thảo luận tiếp nhé kid. Theo mình bài này dùng quay lùi và đặt cận rất có khả năng giải ra. Để cuối tuần mình thử xem sao nhé. Thanks Kid đã quan tâm !

[kidkid]

Quay lai + điều kiện thì hơi khó đấy rox_rook, có nhiều điều kiện . Bài này khó ăn đấy.

[Forlorn_hope]

Mình có ý tưởng thế này:
- Trước hết mình dựa vào dữ liệu dòng để sắp xếp trước. Ví dụ: dữ liệu là 1 2, thì ta tạ sắp xếp: * 0 * *. Như vậy là thỏa mãn có 1 đảo và 1 nhóm đảo gồm 2 đảo.
- Sau khi sắp xếp hết các dòng theo dữ liệu. Ta bắt đầu dựa vào dữ liệu cột để tìm các cách di chuyển dòng sao cho phù hợp. Áp dụng thuật toán quay lui + nhánh cận thì có thể tìm ra đáp án.
Mình mới nghĩ ra thôi, không biết có tối ưu hay không?

[rox_rook]

Hì hì ! Mấy bài dạng này đúng là hành hạ tinh thần! Và đây là cách giải của mình dựa vào ý tưởng quay lùi và đánh giá cận. Khi ta xét hết 1 dòng hay 1 cột thì ta sẽ kiểm tra, chú ý chỗ đặt nhánh với ý tưởng là ta sẽ dễ dàng có được tổng số biển từ dữ liệu vào của bài toán, như vậy nếu tại 1 thời điểm i nào đó, nếu vô tình số biển đi quá dữ liệu thì ta cắt ngay nhánh và chuyển sang hướng khác, tuy nhiên điều kiện này chỉ ở mức tương đối, có lẽ sẽ còn nhiều cách đặt điều kiện hay nữa.

#include <iostream>
using std::endl;
using std::cout;
using std::cin;

#include <fstream>
using std::ifstream;
using std::ofstream;


#include <iomanip>
using std::setw;

#include <cstdlib>/* exit() prototype*/
using std::cerr;

#define FI "Island.inp"
#define maxx 100

using namespace std;

int rowInfo[maxx][maxx],
    colInfo[maxx][maxx],
    ROW[maxx],
    COL[maxx],
    Grid[maxx][maxx],
    sumRowIsland[maxx],
    sumColIsland[maxx];
    
int sizeMap;

void ReadInput()
{
      ifstream inFile ( "Island.inp", ios::in);
      inFile >> sizeMap;
      
      for ( int x = 0; x < sizeMap; x++ ){
            inFile >> ROW[x];
            for ( int y = 0; y < ROW[x]; y++ ){
                  inFile >> rowInfo[x][y];
            }
      }
     
      for ( int x = 0; x < sizeMap; x++ ){
            inFile >> COL[x];
            for ( int y = 0; y < COL[x]; y++ ){
                  inFile >> colInfo[x][y];
            }
      }
      inFile.close();
}
bool checkROW (int rowInfo[][maxx], int rowPosition)
{
      int vaR,   /* Running variables*/ 
          reG,   /* Islands is divided into reG region*/
          isL;   /* The number of Island*/
    
          /*Initilalize info*/
          isL = vaR = reG = 0;
    
      
      while (vaR < sizeMap)
      {
            if (Grid[rowPosition][vaR] == 1)
            {      
                  isL = isL + 1;
            }
            
            if ((Grid[rowPosition][vaR] == 0) || (vaR == sizeMap-1))
            {
                  if (isL > 0)
                  {
                        if (rowInfo[rowPosition][reG] == isL)
                        {
                              isL = 0;       /*Return island = 0, check to the next region*/
                              reG = reG + 1; /*Increase region*/
                        }
                        else
                              return false;
                  }
            }
            vaR = vaR +1; /*Increase until it touches the edge of sizeMap*/
      }
      
      /*If region == orginal Information return true*/
      if (reG == ROW[rowPosition])
        return true;
    
      return false;
}


bool checkCOL ( int colInfo[][maxx], int colPosition)
{
      int vaR,   /* Running variables*/ 
          reG,   /* Islands is divided into reG region*/
          isL;   /* The number of Island*/
    
          /*Initilalize info*/
          isL = vaR = reG = 0;
  
      while (vaR < sizeMap)
      {
            if (Grid[vaR][colPosition] == 1)
            {
                  isL = isL + 1;
            }
            
            if ((Grid[vaR][colPosition] == 0) || (vaR == sizeMap-1))
            {     
                  if (isL > 0)
                  {
                        if (colInfo[colPosition][reG] == isL)
                        {
                              isL = 0; /*Return island = 0, check to the next region*/
                              reG++;   /*Increase region*/
                        }
                        else
                              return false;
                  }
            }
            vaR = vaR + 1;/*Increase until it touches the edge of sizeMap*/
                  
      }
    
      /*If region == orginal Information return true*/
      if (reG == COL[colPosition])
            return true;
    
      return false;
}

void WriteOutput()
{       
      ofstream outFile ( "Island.out", ios::out);
      if ( !outFile )
      {
            cerr << "File could not opened " << endl;
            exit(1);
      }
    
      for ( int x = 0; x < sizeMap; x++){                
            for (int y = 0; y < sizeMap; y++){
                  if (Grid[x][y] == 1)
                        outFile << "*";
                  else  outFile << "~";
            }
            outFile << "\n";
      }
     outFile.close();
}

/*Function calculate Islands is for Branch_Bound technique*/
void CalculateIsland()
{
      for ( int x = 0; x < sizeMap; x++ ){
            for ( int y = 0; y < sizeMap; y++ ){
                  if ( rowInfo[x][y] != 0 ){
                        sumRowIsland[x] += rowInfo[x][y];
                  }
                  else if ( colInfo[x][y] != 0 ){
                        sumColIsland[y] += colInfo[x][y];
                  }
            }
      }
}

void SearchIsland (int xPos, int yPos)
{
      int rowCount,
          colCount;

      rowCount = 0;
      colCount = 0;
      /*Backtrack until it touch the final Horizontal or Vertical*/
      if ((xPos == sizeMap) && (yPos == sizeMap))
      {
        if ( checkROW (rowInfo, xPos) && checkCOL (colInfo, yPos) )
        WriteOutput();
      }
      else
      {
            /*Branch Bound : cut unnessary branches */
            for ( int i = 0; i < yPos; i++ ){
                  if ( Grid[xPos][i] == 1 ){
                        colCount++;
                  }
            }
            for ( int j = 0; j < xPos; j++ ){
                  if ( Grid[j][yPos] == 1 ){
                        rowCount++;
                  }
            }
            
            
           /*If at one point of time, the total of island is over orginal information, break right away*/
            if ( colCount > sumRowIsland[xPos] || rowCount > sumColIsland[yPos] ) ;
      
            
            if (xPos == sizeMap)
            {
                  if (checkCOL (colInfo, yPos))
                        SearchIsland (xPos, yPos+1);
            }
      
            else if (yPos == sizeMap)
            {
                  if (checkROW (rowInfo, xPos))
                        SearchIsland (xPos+1, 0);
            }
            else
            {
                  /*Mark whether is Island or Sea- BackTrack section*/
                  for(int _is = 0; _is <= 1; _is++)
                  {
                        Grid[xPos][yPos] = _is;
                        SearchIsland (xPos, yPos+1);
                  }
            }
      }
}
int main()
{
      ReadInput();
      CalculateIsland();
      SearchIsland (0, 0);
      system("pause");
      return 0;
} 

Nếu ht961711 có cách đánh giá cận chặt chẽ hơn thì cho mình tham khảo nhé ! Thân !

[Forlorn_hope]

Nếu ht961711 có cách đánh giá cận chặt chẽ hơn thì cho mình tham khảo nhé ! Thân !

Những ngày vừa rùi bận quá ko tham gia được. Mình sẽ tham khảo và học hỏi nhiều ở bạn

[nguyenthanhhungcntt]

Hì hì ! Mấy bài dạng này đúng là hành hạ tinh thần! Và đây là cách giải của mình dựa vào ý tưởng quay lùi và đánh giá cận. Khi ta xét hết 1 dòng hay 1 cột thì ta sẽ kiểm tra, chú ý chỗ đặt nhánh với ý tưởng là ta sẽ dễ dàng có được tổng số biển từ dữ liệu vào của bài toán, như vậy nếu tại 1 thời điểm i nào đó, nếu vô tình số biển đi quá dữ liệu thì ta cắt ngay nhánh và chuyển sang hướng khác, tuy nhiên điều kiện này chỉ ở mức tương đối, có lẽ sẽ còn nhiều cách đặt điều kiện hay nữa.

#include <iostream>
using std::endl;
using std::cout;
using std::cin;

#include <fstream>
using std::ifstream;
using std::ofstream;


#include <iomanip>
using std::setw;

#include <cstdlib>/* exit() prototype*/
using std::cerr;

#define FI "Island.inp"
#define maxx 100

using namespace std;

int rowInfo[maxx][maxx],
    colInfo[maxx][maxx],
    ROW[maxx],
    COL[maxx],
    Grid[maxx][maxx],
    sumRowIsland[maxx],
    sumColIsland[maxx];
    
int sizeMap;

void ReadInput()
{
      ifstream inFile ( "Island.inp", ios::in);
      inFile >> sizeMap;
      
      for ( int x = 0; x < sizeMap; x++ ){
            inFile >> ROW[x];
            for ( int y = 0; y < ROW[x]; y++ ){
                  inFile >> rowInfo[x][y];
            }
      }
     
      for ( int x = 0; x < sizeMap; x++ ){
            inFile >> COL[x];
            for ( int y = 0; y < COL[x]; y++ ){
                  inFile >> colInfo[x][y];
            }
      }
      inFile.close();
}
bool checkROW (int rowInfo[][maxx], int rowPosition)
{
      int vaR,   /* Running variables*/ 
          reG,   /* Islands is divided into reG region*/
          isL;   /* The number of Island*/
    
          /*Initilalize info*/
          isL = vaR = reG = 0;
    
      
      while (vaR < sizeMap)
      {
            if (Grid[rowPosition][vaR] == 1)
            {      
                  isL = isL + 1;
            }
            
            if ((Grid[rowPosition][vaR] == 0) || (vaR == sizeMap-1))
            {
                  if (isL > 0)
                  {
                        if (rowInfo[rowPosition][reG] == isL)
                        {
                              isL = 0;       /*Return island = 0, check to the next region*/
                              reG = reG + 1; /*Increase region*/
                        }
                        else
                              return false;
                  }
            }
            vaR = vaR +1; /*Increase until it touches the edge of sizeMap*/
      }
      
      /*If region == orginal Information return true*/
      if (reG == ROW[rowPosition])
        return true;
    
      return false;
}


bool checkCOL ( int colInfo[][maxx], int colPosition)
{
      int vaR,   /* Running variables*/ 
          reG,   /* Islands is divided into reG region*/
          isL;   /* The number of Island*/
    
          /*Initilalize info*/
          isL = vaR = reG = 0;
  
      while (vaR < sizeMap)
      {
            if (Grid[vaR][colPosition] == 1)
            {
                  isL = isL + 1;
            }
            
            if ((Grid[vaR][colPosition] == 0) || (vaR == sizeMap-1))
            {     
                  if (isL > 0)
                  {
                        if (colInfo[colPosition][reG] == isL)
                        {
                              isL = 0; /*Return island = 0, check to the next region*/
                              reG++;   /*Increase region*/
                        }
                        else
                              return false;
                  }
            }
            vaR = vaR + 1;/*Increase until it touches the edge of sizeMap*/
                  
      }
    
      /*If region == orginal Information return true*/
      if (reG == COL[colPosition])
            return true;
    
      return false;
}

void WriteOutput()
{       
      ofstream outFile ( "Island.out", ios::out);
      if ( !outFile )
      {
            cerr << "File could not opened " << endl;
            exit(1);
      }
    
      for ( int x = 0; x < sizeMap; x++){                
            for (int y = 0; y < sizeMap; y++){
                  if (Grid[x][y] == 1)
                        outFile << "*";
                  else  outFile << "~";
            }
            outFile << "\n";
      }
     outFile.close();
}

/*Function calculate Islands is for Branch_Bound technique*/
void CalculateIsland()
{
      for ( int x = 0; x < sizeMap; x++ ){
            for ( int y = 0; y < sizeMap; y++ ){
                  if ( rowInfo[x][y] != 0 ){
                        sumRowIsland[x] += rowInfo[x][y];
                  }
                  else if ( colInfo[x][y] != 0 ){
                        sumColIsland[y] += colInfo[x][y];
                  }
            }
      }
}

void SearchIsland (int xPos, int yPos)
{
      int rowCount,
          colCount;

      rowCount = 0;
      colCount = 0;
      /*Backtrack until it touch the final Horizontal or Vertical*/
      if ((xPos == sizeMap) && (yPos == sizeMap))
      {
        if ( checkROW (rowInfo, xPos) && checkCOL (colInfo, yPos) )
        WriteOutput();
      }
      else
      {
            /*Branch Bound : cut unnessary branches */
            for ( int i = 0; i < yPos; i++ ){
                  if ( Grid[xPos][i] == 1 ){
                        colCount++;
                  }
            }
            for ( int j = 0; j < xPos; j++ ){
                  if ( Grid[j][yPos] == 1 ){
                        rowCount++;
                  }
            }
            
            
           /*If at one point of time, the total of island is over orginal information, break right away*/
            if ( colCount > sumRowIsland[xPos] || rowCount > sumColIsland[yPos] ) ;
      
            
            if (xPos == sizeMap)
            {
                  if (checkCOL (colInfo, yPos))
                        SearchIsland (xPos, yPos+1);
            }
      
            else if (yPos == sizeMap)
            {
                  if (checkROW (rowInfo, xPos))
                        SearchIsland (xPos+1, 0);
            }
            else
            {
                  /*Mark whether is Island or Sea- BackTrack section*/
                  for(int _is = 0; _is <= 1; _is++)
                  {
                        Grid[xPos][yPos] = _is;
                        SearchIsland (xPos, yPos+1);
                  }
            }
      }
}
int main()
{
      ReadInput();
      CalculateIsland();
      SearchIsland (0, 0);
      system("pause");
      return 0;
} 

Nếu ht961711 có cách đánh giá cận chặt chẽ hơn thì cho mình tham khảo nhé ! Thân !

Theo mình nghĩ thì cách code này sẽ không chạy được vì mình cũng copy về rồi chạy mà không thấy gì hệt với lại cái ý tưởng theo mình nghĩ thì đúng nhưng mà cách code thi sai theo mình nghĩ hàm "checkROW " cần tính tất các các khả năng của hàng này tức là liệt kê các cách điền các đảo thoải mãn yêu cầu cuả hàng hàm "SearchIsland " lần lượt sét đến cách điền của từng hàng
Còn nhánh cận sẽ dùng đến cột để loại bỏ những trường hợp chắc chắn sai theo ý tưognr của mình thì hàm "checkROW" sẽ dùngđến thuật toán về tổ hợp chập "Hiểu biết nông cạn mong chỉ giáo"

[rox_rook]

Hì hì, bài này mình làm lâu lắm rùi, bạn cũng tinh ý ghê^^! Mình tin là giải thuật không sai, nhưng cái này mình paste vô sai, sorry nhé, nhưng lỗi này rất dễ phát hiện, bạn suy nghĩ thử xem sao ^^, Hàm checkROW không sai, cái sai của mình là lúc đó mình đã thử tối ưu nó thêm 1 chút nhưng tiếc là nó sai, bài này làm cũng vất vả lắm nên cũng có ấn tượng hì hì ! Dù sao cũng rất cám ơn sự quan tâm của bạn, box giải thuật và cấu trúc dữ liệu nó đang ế ẩm quá đây nè ~~. Đây là output của mình nè :
Input

6
2 1 2
2 3 1
3 1 1 1
1 5
3 2 1 1
1 1

3 1 1 1
2 1 2
1 4
2 2 3
1 2
2 1 2

Output :

*~**~~
~***~*
*~*~*~
~*****
**~*~*
~~~*~~

[rox_rook]

Edit version dùng class, bảo đảm chạy ok T_T :

#include <iostream>#include <fstream>#include <iomanip>#include <cstdlib> class Island{private :    static const int maxx = 100;    int _rrowInfo[maxx][maxx],        _ccolInfo[maxx][maxx],        _rrow[maxx],_ccol[maxx],        _grid[maxx][maxx],        row_value[maxx],        column_value[maxx];    int size; public :    Island();    void read_data_from_file();    bool check_rrow (int _rrowInfo[][maxx], int dx) const;    bool check_ccol ( int _ccolInfo[][maxx], int dy) const;    void print_out_solution() const;    void recursive_searching_island (int xcor, int ycor);    void count_island();}; Island::Island(){    size = 10;    for ( int x = 0; x < maxx; ++x ){        for ( int y = 0; y < maxx; ++y ){            _rrowInfo[x][y] = _ccolInfo[x][y] = 0;            _grid[x][y] = 0;        }        row_value[x] = column_value[x] = 0;        _rrow[x] = _ccol[x] = 0;    }} void Island::read_data_from_file(){    std::ifstream iss("Omg.txt", std::ios::in);    iss >> size;    for(int x = 0; x < size; ++x){        iss >> _rrow[x];        for(int y = 0; y < _rrow[x]; ++y){            iss >> _rrowInfo[x][y];        }    }    for ( int x = 0; x < size; ++x ){        iss >> _ccol[x];        for ( int y = 0; y < _ccol[x]; ++y ){            iss >> _ccolInfo[x][y];        }    }    iss.close();} bool Island::check_rrow(int _rrowInfo[][maxx], int dx) const{    int isL, vaR, reG;    isL = vaR = reG = 0;    while (vaR < size){        if (_grid[dx][vaR] == 1){                  isL = isL + 1;        }                    if ((_grid[dx][vaR] == 0) || (vaR == size-1))        {            if (isL > 0)            {                if (_rrowInfo[dx][reG] == isL)                {                    isL = 0;                           reG = reG + 1;                 }                else                    return false;            }        }        vaR = vaR +1;     }    if (reG == _rrow[dx])        return true;        return false;}  bool Island::check_ccol(int _ccolInfo[][maxx], int dy) const{    int isL, vaR, reG;    isL = vaR = reG = 0;    while (vaR < size)    {        if (_grid[vaR][dy] == 1)        {            isL = isL + 1;        }                    if((_grid[vaR][dy] == 0) || (vaR == size-1))        {                 if(isL > 0)            {                if (_ccolInfo[dy][reG] == isL)                {                    isL = 0;                     reG++;                   }                else                    return false;            }        }        vaR = vaR + 1;    }    if (reG == _ccol[dy])        return true;        return false;} void Island::print_out_solution() const{           for ( int x = 0; x < size; ++x){                        for (int y = 0; y < size; ++y){            if (_grid[x][y] == 1)                std::cout << " * ";            else  std::cout << " ~ ";        }        std::cout << "\n\n";   }}  void Island::count_island(){    for(int x = 0; x < size; ++x)    {        for(int y = 0; y < size; ++y)        {            if(_rrowInfo[x][y] != 0)                row_value[x] += _rrowInfo[x][y];            else if ( _ccolInfo[x][y] != 0)                column_value[y] += _ccolInfo[x][y];        }    }} void Island::recursive_searching_island(int xcor, int ycor){    if ((xcor == size) && (ycor == size))    {        if ( check_rrow (_rrowInfo, xcor) && check_ccol (_ccolInfo, ycor) )        print_out_solution();    }    else{        if (xcor == size)        {            if (check_ccol (_ccolInfo, ycor))                recursive_searching_island (xcor, ycor+1);        }              else if (ycor == size)        {            if (check_rrow (_rrowInfo, xcor))                recursive_searching_island (xcor+1, 0);        }        else{            for(int _is = 0; _is <= 1; _is++)            {                _grid[xcor][ycor] = _is;                recursive_searching_island (xcor, ycor+1);            }        }    }}int main(){    Island oops;    oops.read_data_from_file();    oops.count_island();    oops.recursive_searching_island(0, 0);    return 0;}