UTS Programming Competition 2016 Problem 8

From ProgSoc Wiki

Jump to: navigation, search

This is a part of the UTS Programming Competition 2016 Problem Set.

Problem 8: AMazeIng

Run time limit: 20 seconds

Problem Description

A maze is a convoluted pathway than bends and winds its way around a confined area.

Within a maze you may have regions that are connected to the outside world, either via a direct escape portal or to another region not separated by a wall. These regions form a chain, or path, towards an escape portal.

You might also have regions that are completely surrounded by walls and are therefore not linked to the outside world.

Your task is for each cell in a maze, determine if it is eventually connected to the outside world through any available path. It must not pass through any walls.

Data Specification

Input

A single test case.

The first line will contain two integers. The first integer represents the maze width (1 < W < 9999). The second integer represents the maze height (1 < H < 9999).

This is followed by H lines of W cells. Each cell may contain any or none of the characters N, S, E, W, separated by a TAB character ('\t').

The characters N, S, E W represent open connections. The absence of a letter means there is a wall in that direction:

North: A connection to the cell above

South: A connection to the cell below

East: A connection to the cell to the right

West: A connection to the cell to the left

If a cell has a 'N', then the northern cell is guaranteed to have a corresponding 'S'. The characters will always be in alphabetical order (ENSW).

Output

Reprint the maze, replacing each cells' contents with:

a '#' if a cell is connected to the outside world, or;

a '*' if it is not.

Do not use a separating character (e.g. whitespace) in between cells.

Sample Input

3 3
	NS	
ES	ENW	W
N		

Sample Output

*#*
###
#**

Solutions

Put your solutions here!

Jacob's Java solution

import java.util.*;

class Maze {
	
	public static void main(String[] args) {
		Maze maze = readMaze();
		visitOpenNodes(maze);
		printMaze(maze);
	}
	
	final Node[] nodes;
	final int w, h;
	
	public Maze(int w, int h, Node[] nodes) {
		this.w = w;
		this.h = h;
		this.nodes = nodes;
	}
	
	public Node get(int x, int y) {
		if (nodes[y*w+x] == null)
			throw new IllegalArgumentException(String.format("%d, %d is null", x, y));
		return nodes[y*w+x];
	}
	
	public Node getNeighbor(Node n, char c) {
		if (n.hasCon(c)) { 
			int x = n.x, y = n.y;
			switch (c) {
			case 'N': y--; break;
			case 'S': y++; break;
			case 'W': x--; break;
			case 'E': x++; break;
			}
		
			if (x >= 0 && x < w && y >= 0 && y < h)
				return get(x, y);
		}
		return null;
	}
	
	static void printMaze(Maze m) {
		for (int y = 0; y < m.h; y++) {
			for (int x = 0; x < m.w; x++)
				System.out.print((m.get(x, y).hasBeenVisited()) ? '#' : '*');
			
			System.out.println();
		}
	}
	
	static void visitOpenNodes(Maze m) {
		Queue<Node> nodes = findEdgeOpenings(m);
		for (Node n = nodes.poll(); n != null; n = nodes.poll()) {
			if (!n.hasBeenVisited()) {
				n.markAsVisited();
				addIfUnvisited(m.getNeighbor(n, 'N'), nodes);
				addIfUnvisited(m.getNeighbor(n, 'S'), nodes);
				addIfUnvisited(m.getNeighbor(n, 'E'), nodes);
				addIfUnvisited(m.getNeighbor(n, 'W'), nodes);
			}
		}
	}
	
	static void addIfUnvisited(Node n, Queue<Node> q) {
		if (n != null && !n.hasBeenVisited())
			q.add(n);
	}
	
	static Queue<Node> findEdgeOpenings(Maze m) {
		Queue<Node> cnodes = new LinkedList<Node>();
		for (int x = 0; x < m.w; x++) {
			addIfHasCon(m.get(x, 0), 'N', cnodes);
			addIfHasCon(m.get(x, m.h-1), 'S', cnodes);
		}
		
		for (int y = 0; y < m.h; y++) {
			addIfHasCon(m.get(0, y), 'W', cnodes);
			addIfHasCon(m.get(m.w-1, y), 'E', cnodes);
		}
		
		return cnodes;
	}
	
	static void addIfHasCon(Node n, char c, Queue<Node> queue) {
		if (n.hasCon(c))
			queue.add(n);
	}
	
	static Maze readMaze() {
		Scanner sc = new Scanner(System.in);
		String[] dimensions = sc.nextLine().split(" ");
		int w = Integer.parseInt(dimensions[0]),
		h = Integer.parseInt(dimensions[1]);
		
		Node[] nodes = new Node[w*h];
			
		int y = 0; 
		while (sc.hasNext()) {
			int x = 0;
			for (String con : sc.nextLine().split("\t", -1)) {
				nodes[y*w+x] = new Node(x, y, con);
				x++;
			}
			y++;
		}
		
		return new Maze(w, h, nodes);
	}
		
	static class Node {
		public final String connections;
		public final int x, y;
		private boolean isVisited;
		
		public Node(int x, int y, String connections) {
	 		this.x = x;
			this.y = y;
			this.connections = connections;
		}
		
		public boolean hasBeenVisited() {
			return isVisited;
		}
		
		public void markAsVisited() {
			isVisited = true;
		}
		
		public boolean hasCon(char c) {
			return connections.indexOf(c) >= 0;
		}
		
		public String toString() {
			return String.format("N(%d, %d, %s)", x, y, connections);
		}
	}
}
Personal tools