CareerCup

I think a DAG will do it. Also, to check reverse all the edge-directions and do DFS/BFS from fire-exit. If you're able to reach all of the doors from fire-exit. Bingo!

Problem is not very clear. Still, I came up with a solution.

Construct a graph where the vertices are the rooms, corridors, and fire exits; and the edges are the doors. Naturally these edges are directed in the same way as the corresponding doors.

For the floor design to be valid, any vertex of fire exit should be reachable from every vertex of room.

Reachability in planar graphs (which is the case here) can be computed in O(VlogV) using Thorup's Algorithm. An alternative could be regular DFS or BFS, but they are more expensive.

What means that the door "opens towards the fire exit"? I think that it must to a room which is closer to the fire exit than the previous room.

So, the data structure is the list of graph nodes, where each node has list of all egdes that are incident to it (that is, doors of that room with the direction of each door).

To determine correctness of all doors' directions we can use BFS which uses rooms with fire exits as starting points. Whenever we process a door to an unvisited room, this door must towards the current room. If this rule is violated, then the design is not fire safe.

The complexity of an algorithm is O(V * E), since we visit all rooms and check all the doors once.

Imagine solving this in 40 mins and the guy expected an A* algorithm based solution. I gave a graph based solution.

But the graph has two type of nodes - A room node and exit door node. Each room is connected to other by a directed edge that connects room1 to 2 if the door pushes from 1 to 2. All we need to do is to check from each room if there is atleast one path towards one of the fire exits.
Please note that this graph might not be acyclic.

Doing a BFS starting from one room node, gives the shortest path towards from this room to all the fire exits. If there exits a path to atleast one fire exit in this graph, then it is fine. Doing BFS from all the nodes can solve the problem of verification.

another solution is do a BFS or DFS and get parents of each node in the resulting traversal tree. Then check if there is a path from each room to one of the fire exits.

Need to see how to do this using A* algorithm and a 2d array representation of the room

I'm sorry, what's wrong with using a matrix to store the floor plans?

I'm sorry, what's wrong with using a matrix to store the floor plans?
You would need to find the shortest path to each exit, going through doors first, avoid walls, only walk through floor, then check if the doors open in the direction of that directed path or not, right?

public boolean isOpenedAll(HashMap<Integer, int[]> floor){
	if(floor == null) return false;
	
	for(int[] doors : floor.values()){
		if(isOpenedEach(doors)) return false;
	}
	return true;
}

private boolean isOpenedEach(int[] doors){
	if(doors.length <= 0) return false;
	
	for(int i : doors){
		if(i==0) return false;
	}
	return true;
}

import java.util.ArrayList;


public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		//Room(roomName, hasFireExist)
		Room a = new Room("A", false);
		Room b = new Room("B", false);
		Room c = new Room("C", false);
		Room d = new Room("D", false);
		Room e = new Room("E", false);
		Room f = new Room("F", true);
		Room g = new Room("G", true);
		Room h = new Room("H", true);

		//Room(doorType, roomAccess)
		Door d1 = new Door("push", b);
		Door d2 = new Door("push", c);
		Door d3 = new Door("push", e);
		Door d4 = new Door("pull", h);
		Door d5 = new Door("push", d);
		Door d6 = new Door("push", g);
		Door d7 = new Door("push", f);
		Door d8 = new Door("push", h);
		
		a.addDoor(d1);
		a.addDoor(d2);
		
		b.addDoor(d3);
		c.addDoor(d4);
		
		e.addDoor(d5);
		e.addDoor(d6);
		
		g.addDoor(d7);
		g.addDoor(d8);
		

		checkForAWay(new TreeWay(a,""),0,8);
		
	}
	
	public static class Door
	{
		String type;
		public Room room;

		public Door(String type, Room room)
		{
			this.type = type;
			this.room = room;
		}

		public boolean isPushed()
		{
			return type.equals("push");
		}
	}

	public static class Room
	{
		public String name;
		ArrayList<Door> doors = new ArrayList<Door>();
		boolean hasFireExist;

		public Room(String name, boolean fe)
		{
			this.name = name;
			this.hasFireExist = fe;
		}

		public void setHasFireExist(boolean b)
		{
			hasFireExist = b;
		}

		public void addDoor(Door door)
		{
			doors.add(door);
		}

		public ArrayList<Door> getDoors()
		{
			return doors;
		}
		
		public boolean hasFireExist()
		{
			return hasFireExist;
		}
	}

	public static class TreeWay
	{
		public String wayString;
		public Room room;
		public ArrayList<TreeWay> gotoList = new ArrayList<TreeWay>();

		public TreeWay(Room room,String previousSWay)
		{
			this.room = room;
			wayString = previousSWay+" -> "+room.name;
		}
	}


	public static void checkForAWay(TreeWay tree,int visitedRoom,int roomNbr)
	{
		if(tree.room.hasFireExist())
			{
				System.out.println("YES "+tree.wayString);
			}
		
		boolean allAreClosed = true;
		for(Door door : tree.room.getDoors())
			allAreClosed	=  allAreClosed &&  (!door.isPushed()) ; 

		if((allAreClosed)&&(!tree.room.hasFireExist()))
			{
				System.out.println("BLOCKED "+tree.wayString);
			}
		
		if((visitedRoom>roomNbr)&&(!tree.room.hasFireExist()))
			{
				System.out.println("NO WAY "+tree.wayString);
			}
		
		
		for(Door door : tree.room.getDoors())
			{
				if(door.isPushed())
				{
					TreeWay t = new  TreeWay(door.room,tree.wayString);
					tree.gotoList.add(t);
					checkForAWay(t,visitedRoom+1,roomNbr);
				}		
			}
		
	}
}

Data structure:
A double linked list represents floor, each node is a door, a door has next pointer to represent being pushed towards fire exit, a door has prev pointer to represent being pulled towards fire exit. A door can have either next or prev pointer but not both. A door may optionally have a son pointer which points to a sub-floor. An fire exit has both next and prev pointers.
class Door {
Door* next;
Door* prev;
Door* son;
};

class Floor {
private:
Door* head;
Door* tail;
public:
//
};

Algo:
start from head:
if a node with next only is found, move to its next node (push door, so we expect we meet all push doors until meet a fire exit)
if a node with prev only is found, a wrong pull door is found before fire exit, return failure (0)
if next node has both next and prev, a fire exit is found, stop
if a node has son pointer, recursively checkt the sub-list

start from tail:
if a node with prev only is found, move to its prev node (note: pull door from head direction definition is actually "push" door from tail direction, so we expect we meet all pull doors until meet a fire exit)
if a node with next only is found, a wrong push door is found before fire exit, return failure (0)
if next node has both next and prev, a fire exit is found, stop
if a node has son pointer, recursively checkt the sub-list

note: if start from any Door node:
depend on if it is a push or pull door, execute either of the two loops above (i.e. check all doors on the route towards fire exit has same push/pull attribute)

Only after all are checked and pass, return success (1)

Data structure:
A double linked list represents floor, each node is a door, a door has next pointer to represent being pushed towards fire exit, a door has prev pointer to represent being pulled towards fire exit. A door can have either next or prev pointer but not both. A door may optionally have a son pointer which points to a sub-floor. An fire exit has both next and prev pointers.
class Door {
Door* next;
Door* prev;
Door* son;
};

class Floor {
private:
Door* head;
Door* tail;
public:
//
};

Algo:
start from head:
if a node with next only is found, move to its next node (push door, so we expect we meet all push doors until meet a fire exit)
if a node with prev only is found, a wrong pull door is found before fire exit, return failure (0)
if next node has both next and prev, a fire exit is found, stop
if a node has son pointer, recursively checkt the sub-list

start from tail:
if a node with prev only is found, move to its prev node (note: pull door from head direction definition is actually "push" door from tail direction, so we expect we meet all pull doors until meet a fire exit)
if a node with next only is found, a wrong push door is found before fire exit, return failure (0)
if next node has both next and prev, a fire exit is found, stop
if a node has son pointer, recursively checkt the sub-list

note: if start from any Door node:
depend on if it is a push or pull door, execute either of the two loops above (i.e. check all doors on the route towards fire exit has same push/pull attribute)

Only after all are checked and pass, return success (1)

Data structure:
A double linked list represents floor, each node is a door, a door has next pointer to represent being pushed towards fire exit, a door has prev pointer to represent being pulled towards fire exit. A door can have either next or prev pointer but not both. A door may optionally have a son pointer which points to a sub-floor. An fire exit has both next and prev pointers.
class Door {
Door* next;
Door* prev;
Door* son;
};

class Floor {
private:
Door* head;
Door* tail;
public:
//
};

Algo:
start from head:
if a node with next only is found, move to its next node (push door, so we expect we meet all push doors until meet a fire exit)
if a node with prev only is found, a wrong pull door is found before fire exit, return failure (0)
if next node has both next and prev, a fire exit is found, stop
if a node has son pointer, recursively checkt the sub-list

start from tail:
if a node with prev only is found, move to its prev node (note: pull door from head direction definition is actually "push" door from tail direction, so we expect we meet all pull doors until meet a fire exit)
if a node with next only is found, a wrong push door is found before fire exit, return failure (0)
if next node has both next and prev, a fire exit is found, stop
if a node has son pointer, recursively checkt the sub-list

note: if start from any Door node:
depend on if it is a push or pull door, execute either of the two loops above (i.e. check all doors on the route towards fire exit has same push/pull attribute)

Only after all are checked and pass, return success (1)

Data structure:
A double linked list represents floor, each node is a door, a door has next pointer to represent being pushed towards fire exit, a door has prev pointer to represent being pulled towards fire exit. A door can have either next or prev pointer but not both. A door may optionally have a son pointer which points to a sub-floor. An fire exit has both next and prev pointers.
class Door {
Door* next;
Door* prev;
Door* son;
};

class Floor {
private:
Door* head;
Door* tail;
public:
//
};

Algo:
start from head:
if a node with next only is found, move to its next node (push door, so we expect we meet all push doors until meet a fire exit)
if a node with prev only is found, a wrong pull door is found before fire exit, return failure (0)
if next node has both next and prev, a fire exit is found, stop
if a node has son pointer, recursively checkt the sub-list

start from tail:
if a node with prev only is found, move to its prev node (note: pull door from head direction definition is actually "push" door from tail direction, so we expect we meet all pull doors until meet a fire exit)
if a node with next only is found, a wrong push door is found before fire exit, return failure (0)
if next node has both next and prev, a fire exit is found, stop
if a node has son pointer, recursively checkt the sub-list

note: if start from any Door node:
depend on if it is a push or pull door, execute either of the two loops above (i.e. check all doors on the route towards fire exit has same push/pull attribute)

Only after all are checked and pass, return success (1)

Data structure:
A double linked list represents floor, each node is a door, a door has next pointer to represent being pushed towards fire exit, a door has prev pointer to represent being pulled towards fire exit. A door can have either next or prev pointer but not both. A door may optionally have a son pointer which points to a sub-floor. An fire exit has both next and prev pointers.

Algo:
start from head:
if a node with next only is found, move to its next node (push door, so we expect we meet all push doors until meet a fire exit)
if a node with prev only is found, a wrong pull door is found before fire exit, return failure (0)
if next node has both next and prev, a fire exit is found, stop
if a node has son pointer, recursively checkt the sub-list

start from tail:
if a node with prev only is found, move to its prev node (note: pull door from head direction definition is actually "push" door from tail direction, so we expect we meet all pull doors until meet a fire exit)
if a node with next only is found, a wrong push door is found before fire exit, return failure (0)
if next node has both next and prev, a fire exit is found, stop
if a node has son pointer, recursively checkt the sub-list

note: if start from any Door node:
depend on if it is a push or pull door, execute either of the two loops above (i.e. check all doors on the route towards fire exit has same push/pull attribute)

Only after all are checked and pass, return success (1)

Data structure:
A double linked list represents floor, each node is a door, a door has next pointer to represent being pushed towards fire exit, a door has prev pointer to represent being pulled towards fire exit. A door can have either next or prev pointer but not both. A door may optionally have a son pointer which points to a sub-floor. An fire exit has both next and prev pointers.

Algo:
start from head:
if a node with next only is found, move to its next node (push door, so we expect we meet all push doors until meet a fire exit)
if a node with prev only is found, a wrong pull door is found before fire exit, return failure (0)
if next node has both next and prev, a fire exit is found, stop
if a node has son pointer, recursively checkt the sub-list

start from tail:
if a node with prev only is found, move to its prev node (note: pull door from head direction definition is actually "push" door from tail direction, so we expect we meet all pull doors until meet a fire exit)
if a node with next only is found, a wrong push door is found before fire exit, return failure (0)
if next node has both next and prev, a fire exit is found, stop
if a node has son pointer, recursively checkt the sub-list

note: if start from any Door node:
depend on if it is a push or pull door, execute either of the two loops above (i.e. check all doors on the route towards fire exit has same push/pull attribute)

Only after all are checked and pass, return success (1)