java - 我如何递归搜索房屋布局中的开放空间量？

Question

我正在学习 12 年级的 compsci，并且遇到了一个有关递归的问题。这个问题的背景要求我在给定起始行和列的情况下找到房间中开放空间的数量。

“X”代表墙壁，“O”代表开放空间。开放空间仅在彼此相邻而不是对角线时才计算在内。

给定此房间布局，myHouse.roomSize(1,1) 将返回 21，myHouse.roomSize(5,9) 将返回 5。如果起始行或列是墙，它将返回 0。

 012345678901234567
0XXXXXXXXXXXXXXXXXX
1XOOOOOOXOOOOOOOOOX
2XXXXOOOXOOOOOOOOOX
3XOOOOOOXOOOOOOOOOX
4XOOXXXXOXXXOOOOOOX
5XOOOOXXOOOOXXXOOXX
6XXXXXXXXXXXXXXXXXX

如果有人能给我一些关于如何使用递归解决这个问题的提示

我将非常感激，谢谢。

编辑:这是我到目前为止解决这个问题的尝试，Edit2(现已格式化):将迷宫更改为布局

public int roomSize (int row, int col)
{
    if (layout[row][col] == 'X'|| layout [row][col]== '*')
        return 0;
    if (layout[row][col] == 'O')
    {
    layout[row][col]='*';
    return 1 + roomSize(row + 1, col);
    return 1 + roomSize(row, col + 1);
    return 1 + roomSize(row - 1, col);
    return 1 + roomSize(row, col - 1);
    layout[row][col]='O';
    }
}

Answer 1

伪代码来帮助不想为你做你的工作

int roomSize(int row, int col)
|   bool [x][y] v; //Array to stored visited values x is the width of the maze y is the height
|     set all bools in v to false
|    return doRoomSize(row,col, v) 
end

int doRoomSize(int r, int c, v)
|    if( v[r][c] = true ||  layout [r][c]='X' )
|     | return 0
|    end-if
|    //Now we know that its a good value
|    
|This is a maze type problem so what you need to do is


int roomSize(int row, int col)
|   bool [x][y] v; //Array to stored visited values x is the width of the maze y is the height
|     set all bools in v to false
|    return doRoomSize(row,col, v) 
end

int doRoomSize(int r, int c, v)
|    if( v[r][c] = true ||  layout [r][c]='X' )
|     | return 0
|    end-if
|    //Now we know that its a good value
|    v[r][c] = true; // we have seen this point so we addit to visted
|      int n=1;
|    //Check left
|         n+= doRoomSize(r-1, c)
|    //Check right
|        n+=doRoomSize(r+1,c)
|   //Check up 
|        n+=doRoomSize(r,c-1)
|  // Check down
|        n+=doRoomSize(r,c+1)
|     return n;
end-method