首頁猿問哪種算法最適合對表格的單元格進(jìn)行分組？

哪種算法最適合對表格的單元格進(jìn)行分組？

JavaScript

慕妹3146593 2022-08-18 16:19:42

我有一個(gè)網(wǎng)格，我需要將所有觸摸（包括對角線）合并為組。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| -----------------------------------------我相信已經(jīng)有一個(gè)現(xiàn)有的算法可以使用。我應(yīng)該使用什么算法來解決這個(gè)問題？我嘗試谷歌搜索，但我可能把問題寫錯(cuò)了，沒有得到任何有用的結(jié)果。

查看完整描述

2 回答

莫回?zé)o

TA貢獻(xiàn)1865條經(jīng)驗(yàn) 獲得超7個(gè)贊

一個(gè)簡單的 BFS 在網(wǎng)格上應(yīng)該可以解決問題：

#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){

queue<pair<int, int>> q;

q.push(make_pair(row, col));

vector<pair<int, int>> group;

while(q.size() > 0){

pair<int, int> p = q.front();

q.pop();

if(mark[p.first][p.second]) continue;

mark[p.first][p.second] = 1;

group.push_back(p);

for(int i = -1; i < 2; i++){

for(int j = -1; j < 2; j++){

if(0 > p.first + i) continue;

if(p.first + i >= 5) continue;

if(0 > p.second + j) continue;

if(p.second + j >= 5) continue;

if(mark[p.first + i][p.second + j]) continue;

if(!grid[p.first + i][p.second + j]) continue;

q.push(make_pair(p.first + i, p.second + j));

}

groups.push_back(group);

}

int main(){

groups.clear();

memset(grid, 0, sizeof(grid)); memset(mark, 0, sizeof(mark));

grid[0][0] = 1; grid[0][1] = 1;

grid[2][2] = 1; grid[2][3] = 1; grid[3][3] = 1; grid[3][4] = 1;

for(int i = 0; i < 5; i++){

for(int j = 0; j < 5; j++){

if(mark[i][j]) continue;

if(grid[i][j]) bfs(i, j);

}

for(int i = 0; i < groups.size(); i++){

cout<<"group "<<(i + 1)<<": ";

for(int j = 0; j < groups[i].size(); j++){

cout<<"("<<groups[i][j].first<<", "<<groups[i][j].second<<") ";

}

cout<<endl;

}

return 0;

}

添加了一個(gè)具有 5x5 網(wǎng)格的工作示例，其中 1 表示。x

反對回復(fù) 2022-08-18

www說

TA貢獻(xiàn)1775條經(jīng)驗(yàn) 獲得超8個(gè)贊

您可以訪問所有單元格，并對連接的島嶼使用計(jì)數(shù)器。

function check(array) {

function test(array, i, j, value) {

if (array[i] && array[i][j] === -1) {

array[i][j] = value;

test(array, i - 1, j - 1, value);

test(array, i - 1, j, value);

test(array, i - 1, j + 1, value);

test(array, i + 1, j - 1, value);

test(array, i + 1, j, value);

test(array, i + 1, j + 1, value);

test(array, i, j - 1, value);

test(array, i, j + 1, value);

return true;

}

var value = 1;

array.forEach(a => a.forEach((b, i, bb) => bb[i] = -b));

array.forEach((a, i, aa) => a.forEach((b, j) => test(aa, i, j, value) && value++));

document.getElementById('out').innerHTML += array.map(a => a.join(' ')).join('\n');

}

check([' xx xxxx xx x ', ' xxx xxxx xx xx ', ' x x x x xx ', ' xxx xx xx ', ' x x x xx xx ', 'xxx xxx xx x', 'xx xxx xx xx'].map(s => [...s].map(v => +(v !== ' '))));

反對回復(fù) 2022-08-18