哪种算法最适合对表格的单元格进行分组？

Question

我有一个网格，我需要将所有触摸（包括对角线）合并为组。x

-----------------------------------------
| |x|x| | | | |x|x|x|x| | |x|x| |x| | | |
-----------------------------------------
| |x|x|x| | | |x|x|x|x| | |x|x| |x|x| | |
-----------------------------------------
| |x| | | |x| | | |x| | | |x| | |x|x| | |
-----------------------------------------
| | | | |x|x|x| | | | | |x|x| | |x|x| | |
-----------------------------------------
| |x| | | |x| | | |x| | | |x|x| | |x|x| |
-----------------------------------------
|x|x|x| | | | | |x|x|x| | | |x|x| | | |x|
-----------------------------------------
|x|x| | | | | | | |x|x|x| | |x|x| | |x|x|
-----------------------------------------

我相信已经有一个现有的算法可以使用。我应该使用什么算法来解决这个问题？

---

我尝试谷歌搜索，但我可能把问题写错了，没有得到任何有用的结果。

Answer 1

一个简单的 BFS 在网格上应该可以解决问题：#include <bits/stdc++.h>using namespace std;int grid[5][5];int mark[5][5];vector<vector<pair<int, int> > > groups;void bfs(int row, int col){&nbsp; &nbsp; queue<pair<int, int>> q;&nbsp; &nbsp; q.push(make_pair(row, col));&nbsp; &nbsp; vector<pair<int, int>> group;&nbsp; &nbsp; while(q.size() > 0){&nbsp; &nbsp; &nbsp; &nbsp; pair<int, int> p = q.front();&nbsp; &nbsp; &nbsp; &nbsp; q.pop();&nbsp; &nbsp; &nbsp; &nbsp; if(mark[p.first][p.second]) continue;&nbsp; &nbsp; &nbsp; &nbsp; mark[p.first][p.second] = 1;&nbsp; &nbsp; &nbsp; &nbsp; group.push_back(p);&nbsp; &nbsp; &nbsp; &nbsp; for(int i = -1; i < 2; i++){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for(int j = -1; j < 2; j++){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(0 > p.first + i) continue;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(p.first + i >= 5) continue;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(0 > p.second + j) continue;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(p.second + j >= 5) continue;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(mark[p.first + i][p.second + j]) continue;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(!grid[p.first + i][p.second + j]) continue;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; q.push(make_pair(p.first + i, p.second + j));&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; groups.push_back(group);}int main(){&nbsp; &nbsp; groups.clear();&nbsp; &nbsp; memset(grid, 0, sizeof(grid)); memset(mark, 0, sizeof(mark));&nbsp; &nbsp; grid[0][0] = 1; grid[0][1] = 1;&nbsp; &nbsp; grid[2][2] = 1; grid[2][3] = 1; grid[3][3] = 1; grid[3][4] = 1;&nbsp; &nbsp; for(int i = 0; i < 5; i++){&nbsp; &nbsp; &nbsp; &nbsp; for(int j = 0; j < 5; j++){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(mark[i][j]) continue;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(grid[i][j]) bfs(i, j);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; for(int i = 0; i < groups.size(); i++){&nbsp; &nbsp; &nbsp; &nbsp; cout<<"group "<<(i + 1)<<": ";&nbsp; &nbsp; &nbsp; &nbsp; for(int j = 0; j < groups[i].size(); j++){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; cout<<"("<<groups[i][j].first<<", "<<groups[i][j].second<<") ";&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; cout<<endl;&nbsp; &nbsp; }&nbsp; &nbsp; return 0;}添加了一个具有 5x5 网格的工作示例，其中 1 表示 。x

Answer 2

您可以访问所有单元格，并对连接的岛屿使用计数器。function check(array) {&nbsp; &nbsp; function test(array, i, j, value) {&nbsp; &nbsp; &nbsp; &nbsp; if (array[i] && array[i][j] === -1) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; array[i][j] = value;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; test(array, i - 1, j - 1, value);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; test(array, i - 1, j, value);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; test(array, i - 1, j + 1, value);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; test(array, i + 1, j - 1, value);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; test(array, i + 1, j, value);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; test(array, i + 1, j + 1, value);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; test(array, i, j - 1, value);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; test(array, i, j + 1, value);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return true;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; var value = 1;&nbsp; &nbsp; array.forEach(a => a.forEach((b, i, bb) => bb[i] = -b));&nbsp; &nbsp; array.forEach((a, i, aa) => a.forEach((b, j) => test(aa, i, j, value) && value++));&nbsp; &nbsp; document.getElementById('out').innerHTML += array.map(a => a.join(' ')).join('\n');}check([' xx&nbsp; &nbsp; xxxx&nbsp; xx x&nbsp; &nbsp;', ' xxx&nbsp; &nbsp;xxxx&nbsp; xx xx&nbsp; ', ' x&nbsp; &nbsp;x&nbsp; &nbsp;x&nbsp; &nbsp;x&nbsp; xx&nbsp; ', '&nbsp; &nbsp; xxx&nbsp; &nbsp; &nbsp;xx&nbsp; xx&nbsp; ', ' x&nbsp; &nbsp;x&nbsp; &nbsp;x&nbsp; &nbsp;xx&nbsp; xx ', 'xxx&nbsp; &nbsp; &nbsp;xxx&nbsp; &nbsp;xx&nbsp; &nbsp;x', 'xx&nbsp; &nbsp; &nbsp; &nbsp;xxx&nbsp; xx&nbsp; xx'].map(s => [...s].map(v => +(v !== ' '))));<pre id="out"></pre>