Consider a battlefield to be made up of square cells of unit
dimensions. A soldier on the battlefield can move from a cell to all(8) of its
neighboring cells. soldier has a gun with with him which he can shoot the
targets up to any distance along any of the 8 possible directions
(north,east,west,south,north-east,north- west,south- east,south- west). Also
some sell are bulletproof which prevents bullets to pass but soldier can walk
over them as if it were a normal cell.he can destroy the target from a bulletproof
cell but not from a cell behind it.
Position of a target/ soldier can be given by the cell, they
are on.given the position of the target, starting position of a target and
position of all the bullet proof cells. You have to tell the position of closest
shooting point i.e the cell from which, the soldier can shoot the target and are
closest to the starting position of the soldier. If there are more than such
cells, output all of them.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.TreeSet;
public class BattleFieldGame {
public static void main(final String[] args) {
final int[] input1 = {2, 2};
final int[] input2 = {2, 1};
final int[] input3 = {2, 2};
final String[] input4 = {"1#1", "1#2"};
final String[] result =
nearest_shoot_point(input1, input2, input3, input4);
System.out.println(Arrays.toString(result));
}
public static String[] nearest_shoot_point(final int[] input1,
final int[] input2, final int[] input3, final String[] input4) {
final List<String> block = Arrays.asList(input4);
// block.add("(1,2)");
// block.add("1#2");
final Graph graph = new Graph(input1[0], input1[1], block);
graph.runShortestPathAlgo(input2[0] + "#" + input2[1]);
// final Graph.Vertex vertex = graph.vertexList.get("(3,3)");
final Set<List<Graph.Vertex>> allShortestPaths =
graph.getAllShortestPath(input3[0] + "#" + input3[1]);
final Set<String> output = new TreeSet<String>();
for (final Iterator<List<Graph.Vertex>> iter =
allShortestPaths.iterator(); iter.hasNext();) {
final List<Graph.Vertex> p = (List<Graph.Vertex>)iter.next();
for (int i = 0; i < p.size(); i++) {
if (p.get(i).name.equals(input3[0] + "#" + input3[1])) {
System.out.println(p.get(i - 1).name);
output.add(p.get(i - 1).name);
}
}
System.out.println("");
}
System.out.println("{"
+ output.toString()
.replaceAll("\\[", "")
.replaceAll("\\]", "")
.replaceAll(" ", "") + "}");
return output.toArray(new String[output.size()]);
}
static class Graph {
Map<String, Vertex> vertexList;
private HashSet<List<Vertex>> allShortestPaths;
private List<String> block;
public Graph(final int rows, final int cols, final List<String> block) {
this.vertexList = new HashMap<String, Vertex>();
this.block = block;
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) {
this.vertexList.put(+i + "#" + j, new Vertex(i + "#" + j));
}
}
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) {
setNeibhours(this.vertexList.get(i + "#" + j), i, j);
}
}
}
public void setNeibhours(final Vertex vertex, final int row,
final int col) {
final Vertex right = this.vertexList.get(row + "#" + (col + 1));
final Vertex left = this.vertexList.get(row + "#" + (col - 1));
final Vertex up = this.vertexList.get((row - 1) + "#" + col);
final Vertex down = this.vertexList.get((row + 1) + "#" + col);
final Vertex leftTop =
this.vertexList.get((row - 1) + "#" + (col - 1));
final Vertex rightTop =
this.vertexList.get((row - 1) + "#" + (col + 1));
final Vertex bottamLeft =
this.vertexList.get((row + 1) + "#" + (col - 1));
final Vertex bottamRight =
this.vertexList.get((row + 1) + "#" + (col + 1));
if (right != null && !this.block.contains(right.name)) {
vertex.neibhours.put(right, 1);
}
if (left != null && !this.block.contains(left.name)) {
vertex.neibhours.put(left, 1);
}
if (up != null && !this.block.contains(up.name)) {
vertex.neibhours.put(up, 1);
}
if (down != null && !this.block.contains(down.name)) {
vertex.neibhours.put(down, 1);
}
if (rightTop != null && !this.block.contains(rightTop.name)) {
vertex.neibhours.put(rightTop, 1);
}
if (leftTop != null && !this.block.contains(leftTop.name)) {
vertex.neibhours.put(leftTop, 1);
}
if (bottamLeft != null && !this.block.contains(bottamLeft.name)) {
vertex.neibhours.put(bottamLeft, 1);
}
if (bottamRight != null && !this.block.contains(bottamRight.name)) {
vertex.neibhours.put(bottamRight, 1);
}
}
class Vertex implements Comparable<Vertex> {
String name;
int sourceDistance = Integer.MAX_VALUE;
Vertex previous;
List<Vertex> prev = new ArrayList<Vertex>();
HashMap<Vertex, Integer> neibhours = new HashMap<Vertex, Integer>();
public Vertex(final String name) {
this.name = name;
}
public int compareTo(final Vertex other) {
// TODO Auto-generated method stub
return Double.compare(this.sourceDistance, other.sourceDistance);
}
}
public void runShortestPathAlgo(final String source) {
final Vertex sourceVer = this.vertexList.get(source);
sourceVer.sourceDistance = 0;
final PriorityQueue<Vertex> queue = new PriorityQueue<Vertex>();
queue.add(sourceVer);
List<Vertex> prev = null;
while (!queue.isEmpty()) {
final Vertex u = queue.poll();
for (final Map.Entry<Vertex, Integer> nvEntry : u.neibhours.entrySet()) {
final Vertex nv = nvEntry.getKey();
prev = nv.prev;
final int distanceThroughU = u.sourceDistance + 1;
if (distanceThroughU < nv.sourceDistance) {
queue.remove(nv);
nv.sourceDistance = distanceThroughU;
nv.previous = u;
queue.add(nv);
prev = new ArrayList<Vertex>();
prev.add(u);
nv.prev = prev;
} else if (distanceThroughU == nv.sourceDistance) {
if (prev != null)
prev.add(u);
else {
prev = new ArrayList<Vertex>();
prev.add(u);
nv.prev = prev;
}
}
}
}
}
public Set<List<Vertex>> getAllShortestPath(final String target) {
final Vertex targetVer = this.vertexList.get(target);
this.allShortestPaths = new HashSet<List<Vertex>>();
getShortestPath(new ArrayList<Vertex>(), targetVer);
return this.allShortestPaths;
}
private List<Vertex> getShortestPath(final List<Vertex> shortestPath,
final Vertex targetVer) {
final List<Vertex> prev = targetVer.prev;
if (prev == null || prev.isEmpty()) {
shortestPath.add(targetVer);
Collections.reverse(shortestPath);
this.allShortestPaths.add(shortestPath);
} else {
final List<Vertex> updatedPath =
new ArrayList<Vertex>(shortestPath);
updatedPath.add(targetVer);
for (final Iterator<Vertex> iterator = prev.iterator(); iterator.hasNext();) {
final Vertex vertex = (Vertex)iterator.next();
getShortestPath(updatedPath, vertex);
}
}
return shortestPath;
}
}
}
Kindly provide your valuable feedback in comment box.
No comments:
Post a Comment