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;
}
}
没有评论:
发表评论