中兴捧月蓝剑题解

第一题

问题大概是说，有一堆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