Xác định số Miền Lớn Nhất trong lập trình C/C++

[kidkid]

Không biết nói sau. Cho cái ví dụ thế này:

1 1 1 2 2 2 3 2
1 1 2 2 3 3 3 1
2 2 2 2 1 1 1 1
2 2 2 2 2 1 1 1

Đề bài yêu cầu là nêu ra số miền, và giá trị miền lớn nhất.
Miền là tập hợp những phần tử gần nhau ( ngang, dọc ) có cùng giá trị n ( n từ 1-10). miền lớn nhất là miền có nhiều phần tử nhất.

File vào có dạng :
n m với n là số pt trên hàng, m là cột .
các hàng tiếp theo thể hiện như vd.

File ra có dạng :
x : số miền. y là số phần tử miền lớn nhất.


Lâu rồi, thảo luận lại cho nó vui tí. he he

[rox_rook]

Bài này r2 nghĩ thuật toán loang T_T, khỏi chạy đi đâu được hết !

[Tarzan]

nếu kích thước nhỏ vậy, thì in ra màn hình mà nhìn ).

[NT_OnlyLove]

Bài này r2 nghĩ thuật toán loang T_T, khỏi chạy đi đâu được hết !

Hôm trước bàn luận bài bên kia, rr nói sẽ code. Vậy xong chưa post lên mọi người trao đổi coi.
Mình cũng không có thời gian nên cũng chưa có code được.

[rox_rook]

Hôm trước bàn luận bài bên kia, rr nói sẽ code. Vậy xong chưa post lên mọi người trao đổi coi.
Mình cũng không có thời gian nên cũng chưa có code được.

No more coding T_T! Everybody complained !!!

[rox_rook]

Lần sau không có khích tướng nữa nha OnlyLove T_T :

#include <iostream>#include <vector>typedef unsigned int USI;typedef std::vector<int> values;typedef values::iterator _pointer;typedef values::const_iterator _constPtr;static int matrix[6][10] = { {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1},                             {-1,  1,  1,  1,  2,  2,  2,  3,  2, -1},                             {-1,  1,  1,  2,  2,  3,  3,  3,  1, -1},                             {-1,  2,  2,  2,  2,  1,  1,  1,  1, -1},                             {-1,  2,  2,  2,  2,  2,  1,  1,  1, -1},                             {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}  }; void RecursiveCounting(USI xCor, USI yCor, int _type, _pointer _updatedArea){    matrix[xCor][yCor] = -1;    *_updatedArea = *_updatedArea + 1;     // *-case [xCor + 1][yCor]    if(matrix[xCor + 1][yCor] == _type && matrix[xCor + 1][yCor] != -1)         RecursiveCounting(xCor + 1, yCor, _type, _updatedArea);             // *-case [xCor - 1][yCor]    if(matrix[xCor - 1][yCor] == _type && matrix[xCor  - 1][yCor] != -1)         RecursiveCounting(xCor - 1, yCor, _type, _updatedArea);         // *-case [xCor][yCor +  1]    if(matrix[xCor][yCor + 1] == _type && matrix[xCor][yCor +  1] != -1)         RecursiveCounting(xCor, yCor + 1, _type, _updatedArea);      // *-case [xCor][yCor -  1]    if(matrix[xCor][yCor - 1] == _type && matrix[xCor][yCor -  1] != -1)         RecursiveCounting(xCor, yCor - 1, _type, _updatedArea); } void FindingMaximumArea(int type, _pointer _sArea, USI _srow, USI _scol){    int maximum_area = 0;    for(int dx = 1; dx <= _srow; ++dx)    {        for(int dy = 1; dy <= _scol; ++dy)        {            if(matrix[dx][dy] != -1 && matrix[dx][dy] == type)            {                *_sArea = 0;                RecursiveCounting(dx, dy, type, _sArea);                if(*_sArea > maximum_area)                    maximum_area = *_sArea;            }        }    }    *_sArea = maximum_area;}                int main(){    USI max_value = 0;    const USI _srow = 4;    const USI _scol = 8;    values _Area(3, 0);    values _typeArea;    _typeArea.push_back(1);    _typeArea.push_back(2);    _typeArea.push_back(3);        USI _next = 0;    for(_pointer iss = _Area.begin(); iss != _Area.end(); ++iss){        FindingMaximumArea(_typeArea[_next], iss, _srow, _scol);        _next = _next + 1;    }    for(_constPtr iss = _Area.begin(); iss != _Area.end(); ++iss){        if(max_value < *iss)            max_value = *iss;    }        std::cout << "The largest domain : " << max_value << "\n";    return 0;}

[kidkid]

OK chính xác, mặc dù cậu code khó hiểu, nhưng ok. Có điều với bài này còn cách nào khác hay ko ?

Bài này có 2 cách ( tớ biết )
+ 1, áp dụng các thuật toán như dfs,bfs để giải quyết ( R2 - DFS (ko phải loang nhé. ))
+ 2, quy về đồ thị.

[rox_rook]

Code bài đó viết quá ngu T_T, đúng là vội chẳng có kết quả gì, this one is 100% more efficient and much easier to read T_T :

#include <iostream>#include <vector> typedef unsigned int USI;static int matrix[6][10] = { {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1},                             {-1,  1,  1,  1,  2,  2,  2,  3,  2, -1},                             {-1,  1,  1,  2,  2,  3,  3,  3,  1, -1},                             {-1,  2,  2,  2,  2,  1,  1,  1,  1, -1},                             {-1,  2,  2,  2,  2,  2,  1,  1,  1, -1},                             {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1} }; void RecursiveCounting(USI xCor, USI yCor, int _type, USI& _updatedArea){  matrix[xCor][yCor] = -1;  _updatedArea = _updatedArea + 1;   // *-case [xCor + 1][yCor]  if(matrix[xCor + 1][yCor] == _type && matrix[xCor + 1][yCor] != -1)    RecursiveCounting(xCor + 1, yCor, _type, _updatedArea);         // *-case [xCor - 1][yCor]  if(matrix[xCor - 1][yCor] == _type && matrix[xCor  - 1][yCor] != -1)    RecursiveCounting(xCor - 1, yCor, _type, _updatedArea);     // *-case [xCor][yCor +  1]  if(matrix[xCor][yCor + 1] == _type && matrix[xCor][yCor +  1] != -1)    RecursiveCounting(xCor, yCor + 1, _type, _updatedArea);   // *-case [xCor][yCor -  1]  if(matrix[xCor][yCor - 1] == _type && matrix[xCor][yCor -  1] != -1)    RecursiveCounting(xCor, yCor - 1, _type, _updatedArea);} void FindingMaximumArea(USI _srow, USI _scol, USI& _sArea){  int maximum_area = 0;  for(int dx = 1; dx <= _srow; ++dx){    for(int dy = 1; dy <= _scol; ++dy){      switch(matrix[dx][dy])      {        case 1 :          if(matrix[dx][dy] != -1 && matrix[dx][dy] == 1){            _sArea = 0;            RecursiveCounting(dx, dy, 1, _sArea);            if(_sArea > maximum_area)              maximum_area = _sArea;          }          break;        case 2 :          if(matrix[dx][dy] != -1 && matrix[dx][dy] == 2){            _sArea = 0;            RecursiveCounting(dx, dy, 2, _sArea);            if(_sArea > maximum_area)              maximum_area = _sArea;          }          break;        default : //i.e case 3          if(matrix[dx][dy] != -1 && matrix[dx][dy] == 3){            _sArea = 0;            RecursiveCounting(dx, dy, 3, _sArea);            if(_sArea > maximum_area)              maximum_area = _sArea;          }          break;      }    }  }  _sArea = maximum_area;}                   int main(){  USI max_value = 0;  const USI _srow = 4;  const USI _scol = 8;      FindingMaximumArea(_srow, _scol, max_value);  std::cout << "The largest domain : " << max_value << "\n";   return 0;}

[kidkid]

Cậu lại sai nữa rồi . R2 à, chỉ có ý đúng thôi.

[rox_rook]

Cậu lại sai nữa rồi . R2 à, chỉ có ý đúng thôi.

Sai chỗ nào vậy Kid ?

+ 1, áp dụng các thuật toán như dfs,bfs để giải quyết ( R2 - DFS (ko phải loang nhé. ))
+ 2, quy về đồ thị.

DFS và BFS là các thuật toán cơ bản trên đồ thị mà ? DFS = loang = tìm kiếm theo chiều sâu ? Cái này thì mình làm bài rùi thấy nó ghi thế, vì bản chất loang là quét duyệt theo DFS.