z***2
发帖数: 66 | 1 8 -1 4
3 -1 -1
5 2 2
total region =2， 一個是 83522. 另一個是4，
-1就是 當 一個 分隔區域的 separator
如何最快就出一個 given 2d matrix 有多少個 regions? DFS? run time = ???
謝謝 | u******g
发帖数: 89 | 2 你要最快的话可能是disjoint set吧。。？ | r**h
发帖数: 1288 | 3 我的想法是，首先从任意一个非separator的点开始，做dfs分离出一个region。途中将
所有遇到的separator送进一个队列。然后每次从队列里面送出一个separator，遍历和
他相邻的还未被访问的其他region，或者将和他相邻的还未入过队列的separator入队
。直到队列变成空。
总时间复杂度是matrix的元素个数。
【在 z***2 的大作中提到】
: 8 -1 4
: 3 -1 -1
: 5 2 2
: total region =2， 一個是 83522. 另一個是4，
: -1就是 當 一個 分隔區域的 separator
: 如何最快就出一個 given 2d matrix 有多少個 regions? DFS? run time = ???
: 謝謝
| f******t
发帖数: 18 | 4 这样？O(n)，n是matrix元素数目
void dfs(hash_set&s, vector>& matrix,int row,int col)
{
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
s.insert(row*matrix[0].size()+col);
for(int i=0;i<4;i++)
{
int newRow = row+dir[i][0],newCol = col+dir[i][1];
if(newRow>=0&&new
newCol>=0&&newCol
matrix[newRow][newCol]!=-1)
dfs(s,matrix,newRow,newCol);
}
}
int regionNum(vector>& matrix)
{
//special case return
hash_set s;
int region = 0;
for(int i=0;i
for(int j=0;j
if(s.find(i*matrix[0].size()+j)!=s.end()&&matrix[i][j]!=-1)
{
dfs(s,matrix,i,j);
region++;
}
return region;
} | r**h
发帖数: 1288 | 5 是哦。。。直接找未遍历的分区中某一点就行
我想复杂了。。
【在 f******t 的大作中提到】
: 这样？O(n)，n是matrix元素数目
: void dfs(hash_set&s, vector>& matrix,int row,int col)
: {
: int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
: s.insert(row*matrix[0].size()+col);
: for(int i=0;i<4;i++)
: {
: int newRow = row+dir[i][0],newCol = col+dir[i][1];
: if(newRow>=0&&new: newCol>=0&&newCol
| l**b
发帖数: 457 | | y*******o
发帖数: 6632 | 7 8 -1 4
3 3 -1
5 2 2
will be 1 region?
【在 z***2 的大作中提到】
: 8 -1 4
: 3 -1 -1
: 5 2 2
: total region =2， 一個是 83522. 另一個是4，
: -1就是 當 一個 分隔區域的 separator
: 如何最快就出一個 given 2d matrix 有多少個 regions? DFS? run time = ???
: 謝謝
| b******z
发帖数: 410 | 8 Should the loop if condition:
S.find() == s.end?
【在 f******t 的大作中提到】
: 这样？O(n)，n是matrix元素数目
: void dfs(hash_set&s, vector>& matrix,int row,int col)
: {
: int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
: s.insert(row*matrix[0].size()+col);
: for(int i=0;i<4;i++)
: {
: int newRow = row+dir[i][0],newCol = col+dir[i][1];
: if(newRow>=0&&new: newCol>=0&&newCol
| Z**********4
发帖数: 528 | | y***g
发帖数: 1492 | 10 dfs bfs无所谓吧 color-fill能遍历就行 |
|
