2015年8月9日星期日

[吐槽][口袋宝石] Room isConnected

package is.room.connected;

//How to calculate the time complexity of an algorithm using queue (or other data structure)?

//The time complexity of BFS is greater than DFS. Because the positions are enqueued multiple times?
//If use DFS the enqueued positions will never be enqueued again.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution {
    public static void main(String[] args) {
        List<Room> rooms = new ArrayList<Room>();
        rooms.add(new Room(0,0,5,5));
        rooms.add(new Room(5,4,1,1));
        System.out.println(isConnected(rooms, 9, 9));
    }
    
    public static boolean isConnected(List<Room> rooms, int m, int n) {
        if (rooms == null || rooms.size() == 0) {
            return false;
        }
        boolean[][] board = new boolean[m][n];
        
        //Calaulate the area of all the rooms
        int area = 0;
        for (Room r : rooms) {
            area += r.h * r.w;
            for (int i = r.x; i < r.x + r.w && i < m; i++) {
                for (int j = r.y; j < r.y + r.h && j < n; j++) {
                    board[i][j] = true;
                }
            }
        }
        
        //Use BFS to traverse start from the first room, take down the area of it
        Queue<Coordinate> queue = new LinkedList<Coordinate>();
        queue.offer(new Coordinate(rooms.get(0).x, rooms.get(0).y));
        
        int bfs_area = 0;
        while (!queue.isEmpty()) {
            Coordinate tmp = queue.poll();
            bfs_area += board[tmp.x][tmp.y] ? 1 : 0;
            board[tmp.x][tmp.y] = false;
            
            if (tmp.x + 1 < m && board[tmp.x + 1][tmp.y]) {
                queue.offer(new Coordinate(tmp.x + 1, tmp.y));
            }
            if (tmp.x - 1 >= 0 && board[tmp.x - 1][tmp.y]) {
                queue.offer(new Coordinate(tmp.x - 1, tmp.y));
            }
            if (tmp.y + 1 < n && board[tmp.x][tmp.y + 1]) {
                queue.offer(new Coordinate(tmp.x, tmp.y + 1));
            }
            if (tmp.y - 1 >= 0 && board[tmp.x][tmp.y - 1]) {
                queue.offer(new Coordinate(tmp.x, tmp.y - 1));
            }
        }

        return area == bfs_area;
    }
}


package is.room.connected;

public class Room {
    int x, y, w, h;
    
    //Assume (x, y) is the left bottom of the room
    //h is the height of the room
    //w is the width of the room
    
    public Room(int x, int y, int w, int h) {
        this.x = x;
        this.y = y;
        this.w = w;
        this.h = h;
    }
}


package is.room.connected;

public class Coordinate {
    int x;
    int y;
    
    public Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

没有评论:

发表评论