p**e
发帖数: 533 | 1 一个bitmap（matrix array). 上面有很多area shapes （每个shape的颜色是一样的
），但是不相连的shapes可能是同样的颜色，怎么找到面积最大的shape？ |
p*****2
发帖数: 21240 | 2
bitmap又是matrix array？没看懂。能解释一下吗？感觉像是DFS的题。
【在 p**e 的大作中提到】
: 一个bitmap（matrix array). 上面有很多area shapes （每个shape的颜色是一样的
: ），但是不相连的shapes可能是同样的颜色，怎么找到面积最大的shape？
|
g*********e
发帖数: 14401 | 3 用另一个visited array来记录已经走过的bit。然后对没走过的bit dfs/bfs,同时
maintain最大面积 |
p**e
发帖数: 533 | 4 一样的，就是bitmap以array的形式存pixel。
【在 p*****2 的大作中提到】
:
: bitmap又是matrix array？没看懂。能解释一下吗？感觉像是DFS的题。
|
p*****2
发帖数: 21240 | 5
那就DFS就可以了。
【在 p**e 的大作中提到】
: 一样的，就是bitmap以array的形式存pixel。
|
p**e
发帖数: 533 | 6 能具体说说怎么走？从左到右？还是从上到下？
怎么确定一个area？
怎么得到一个shape（包括不规则的）的面积？
【在 g*********e 的大作中提到】
: 用另一个visited array来记录已经走过的bit。然后对没走过的bit dfs/bfs,同时
: maintain最大面积
|
p*****2
发帖数: 21240 | 7
比如随便找一个点。从这个点开始找周围的点，一共8个邻居。如果是相同颜色的就继
续往下找。最后找不到的时候就把这个shape找全了。
【在 p**e 的大作中提到】
: 能具体说说怎么走？从左到右？还是从上到下？
: 怎么确定一个area？
: 怎么得到一个shape（包括不规则的）的面积？
|
h****e
发帖数: 928 | 8 各个方向都要试过去。BFS/DFS + backtracking
类似的题目很多：
http://www.geeksforgeeks.org/archives/13376
【在 p**e 的大作中提到】
: 能具体说说怎么走？从左到右？还是从上到下？
: 怎么确定一个area？
: 怎么得到一个shape（包括不规则的）的面积？
|
s******n
发帖数: 3946 | 9 写一个练练
int a[m][n];
bool findcolorelement(int& x, int& y)
{
for (int i=x; i
for (int j=y; j
if (a[i][j]) {
x = i;
y = j;
return true;
}
return false;
}
int findareasize(int x, int y, int color) {
if (x<0||y<0||x>=m||y>=n||color!=a[x][y]) return 0;
a[x][y]=0;
return 1+findarea(x-1,y,color)+findarea(x,y-1,color)
+findarea(x+1,y,color)+findarea(x,y+1,color);
}
int main()
{
int largestarea = 0;
int x=0;
int y=0;
while (findcolorelement(x,y))
{
lagestarea = max(lagestarea, findareasize(x,y,a[x][y]));
}
printf("largest area %d\n", largestarea);
} |
p**e
发帖数: 533 | 10 这个findareasize是从哪里到哪里的size？
这个recursive function 感觉有问题，好像会陷入死循环。
int findareasize(int x, int y, int color) {
if (x<0||y<0||x>=m||y>=n||color!=a[x][y]) return 0;
a[x][y]=0;
return 1+findarea(x-1,y,color)+findarea(x,y-1,color)
+findarea(x+1,y,color)+findarea(x,y+1,color);
}
【在 s******n 的大作中提到】
: 写一个练练
: int a[m][n];
: bool findcolorelement(int& x, int& y)
: {
: for (int i=x; i: for (int j=y; j: if (a[i][j]) {
: x = i;
: y = j;
: return true;
|
p**e
发帖数: 533 | 11 如果一个节点的两个子节点分别是右边的和下面的，感觉BFS或者DFS就可以了，
需要backtracking跟他们相结合吗？一起用的优势是什么？
另外，BFS或者DFS是不是很多节点都被扫过多次？有没有办法保证只扫过一次？
【在 h****e 的大作中提到】
: 各个方向都要试过去。BFS/DFS + backtracking
: 类似的题目很多：
: http://www.geeksforgeeks.org/archives/13376
|
h*******n
发帖数: 614 | 12 aglee。。。
【在 g*********e 的大作中提到】
: 用另一个visited array来记录已经走过的bit。然后对没走过的bit dfs/bfs,同时
: maintain最大面积
|
