【滴滴笔试】大神看一下哪里有问题

```
public class test1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int row = sc.nextInt(); sc.nextLine();
        int column = sc.nextInt(); sc.nextLine();
        int num = sc.nextInt(); sc.nextLine();
        LandMap landMap = new LandMap(row, column);
        ArrayList<Integer> out = new ArrayList<>();
        for (int i = 0; i < num; i++) {
            String[] temp = sc.nextLine().split(" ");
            Integer positionX = Integer.valueOf(temp[0]);
            Integer positionY = Integer.valueOf(temp[1]);
            out.add(landMap.solve(positionX, positionY));
        }
        for (int i = 0; i < out.size(); i++) {
            if (i ==  out.size()- 1) {
                System.out.print(out.get(i));
            } else {
                System.out.print(out.get(i)+" ");
            }
        }

    }
}

class LandMap{
    static int[][] map;
    static int count;
    int row;
    int column;
    public LandMap(int row,int column){
        this.row = row;
        this.column = column;
        count = 0;
        map= new int[row][column];

    }
    public int solve(int row, int column) {
        if (row<0||row>=this.row||column<0||column>=this.column) return count;
        map[row][column] = 1;
        if (isWater(row - 1, column) && isWater(row + 1, column)
                && isWater(row, column - 1) && isWater(row, column + 1)) {
            count++;
            return count;
        } else {
            return count;
        }
    }

    private boolean isWater(int row, int column) {
        if (row<0||row>=this.row||column<0||column>=this.column) return true;
        return map[row][column] == 0;
    }
}

```
大致的思路就是:

在LandMap中维护一个二维数组,当一个点的上下左右的值都为默认值0或者越界的时候,标记为这个点岛屿。count++

当新的点和他相邻的时候因为相邻所以新的点视为这个点的扩充,count不变
结果a了40%

全部评论
懒得看代码,你是否考虑,新的点链接了两个或多个原本分离的岛屿?
点赞 回复 分享
发布于 2017-09-23 21:15
你是韩宇航?
点赞 回复 分享
发布于 2017-09-23 21:17
考虑连接多个岛屿的情况 已经连接的多个部分可能是同一个岛屿的情况,具体如图: # 代表岛屿,= 代表水面,*代表此次add_land的位置 情况1:岛屿数量减1 = # = = = # * = = = 情况2:岛屿数量不变 # # = = = # * = = =
点赞 回复 分享
发布于 2017-09-23 21:16

相关推荐

点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务