盒子
盒子
Posts List
  1. 第一题
  2. 第二题

中兴捧月蓝剑第一题题解

第一题

问题大概是说,有一堆1和0,1表示房子,0表示空地,要求是连续几个1(不包括对角线)的四周(上下左右左上左下右上右下)都是0的成为美丽房子。

简单的使用dfs即可。然后注意判断存在对角线的不算

int m, n;
int flag;
int beautifulhouse(char** grid, int gridRowSize, int gridColSize) {
    m = gridRowSize;
    n = gridColSize;
    if(m == 0) return 0;
    if(n == 0) return 0;
    int result = 0;
    for(int i = 0; i < gridRowSize; i++) {
        for(int j = 0;j < gridColSize;j++) {
            if(grid[i][j] != 1) continue;
            flag = 0
            result++;
            dfs(grid, i, j);
            result -= flag;
        }
    }
    return result;

}
void dfs(char** grid, int i, int j) {
    if(i < 0 || j < 0 || i >= m || j >= n) return;
    if(grid[i][j] == 1) {
        grid[i][j] = 2;
        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
        if(i < m - 1 && j < n - 1 && grid[i + 1][j + 1] == 1) {
        flag = 1;
        dfs(grid, i + 1, j + 1);
        }
         if(i < m - 1 && j > 0 && grid[i + 1][j - 1] == 1) {
        flag = 1;
        dfs(grid, i + 1, j - 1);
        }
    }
}

第二题

bst的一条路径,没什么可以说的。

呼呼呼山

Jun 12, 2016 8:37 PM