Problem statement:
http://community.topcoder.com/stat?c=problem_statement&pm=10808&rd=14234
I used permutation code from:
http://www.cs.utexas.edu/users/djimenez/utsa/cs3343/lecture25.html
SRM 481 - TopCoder Wiki:
http://apps.topcoder.com/wiki/pages/viewpage.action?pageId=45188543&navigatingVersions=true
public class Cafeteria
{
int sx, sy;
int T = 14 * 60 + 30;
int q, r;
public String latestTime(int[] offset, int[] walkingTime, int[] drivingTime)
{
int N = offset.length;
int[] times = new int[N];
int maxTime = Integer.MIN_VALUE, idx = -1;
for(int i = 0; i < N; i++) {
int temp = Math.abs(T - drivingTime[i]);
int q = temp / 60;
int r = temp % 60;
for(int o = 50 + offset[i]; ; o -= 10) if(o <= r) {
temp = (o + q * 60) - walkingTime[i];
break;
}
times[i] = temp;
if(times[i] > maxTime) {
maxTime = times[i];
idx = i;
}
}
q = times[idx] / 60;
if(q > 12) q -= 12;
r = times[idx] % 60;
String sq = (q < 10) ? "0"+q : ""+q;
String sr = (r < 10) ? "0"+r : ""+r;
return sq + ":" + sr;
}
public static void main(String[] args)
{
Cafeteria c = new Cafeteria();
int[] offset = {9};
int[] walkingTime = {1};
int[] drivingTime = {1};
System.out.println(c.latestTime(offset, walkingTime, drivingTime));
System.out.println(c.latestTime(
new int[]{6},
new int[]{9},
new int[]{120}));
System.out.println(c.latestTime(
new int[]{6,9},
new int[]{9,10},
new int[]{120,121}));
System.out.println(c.latestTime(
new int[]{0,1,2,3,4,5,6,7,8,9},
new int[]{11,11,11,11,11,11,11,11,11,11},
new int[]{190,190,190,190,190,190,190,190,190,190}));
System.out.println(c.latestTime(
new int[]{7,4,0,0,2,1,6,7,7,0,8,6,0,5,0,6,7,9,0,2,4,8,4,7,
9,2,4,4,3,1,4,5,8,8,2,5,7,8,7,5,6,8,8,0,1,3,5,0,8},
new int[]{26,14,1,4,16,28,16,6,4,5,21,18,5,2,21,21,28,22,5,22,26,16,14,
19,19,19,4,12,24,4,30,16,28,20,25,2,30,18,4,6,9,22,8,3,7,29,8,30,6},
new int[]{151,264,280,89,63,57,15,120,28,296,76,269,90,106,31,222,
291,52,102,73,140,248,44,187,76,49,296,106,54,119,54,283,263,
285,275,127,108,82,84,241,169,203,244,256,109,288,9,262,103}));
}
}
package srm207.round1;
import java.util.LinkedList;
public class CaptureThemAll
{
public static void main(String[] args) {
new CaptureThemAll().solve();
}
public void solve()
{
fastKnight("a1", "b3", "c5");
fastKnight("b1", "c3", "a3");
fastKnight("a1", "a2", "b2");
fastKnight("a5", "b7", "e4");
fastKnight("h8", "e2", "d2");
}
public int fastKnight(String knight, String rook, String queen)
{
int[] k = strToIntArray(knight);
int[] r = strToIntArray(rook);
int[] q = strToIntArray(queen);
int min1 = min(k, r) + min(r, q);
int min2 = min(k, q) + min(q, r);
int min = (min1 < min2) ? min1 : min2;
System.out.println(min);
return min;
}
public int min(int[] from, int[] to)
{
int min = 0;
LinkedList ks = new LinkedList<>();
ks.add(from);
int[][] visited = new int[64][2];
int[] levelMin = new int[100];
levelMin[0] = 1;
int levelMinIdx = 0;
int lastIndex = -1;
int jumpidx = 0;
while(!ks.isEmpty())
{
if(lastIndex != levelMinIdx) {
min++;
lastIndex = levelMinIdx;
}
from = ks.poll();
levelMin[levelMinIdx]--;
if(levelMin[levelMinIdx] == 0) {
levelMinIdx++;
}
visited = addToVisited(from, visited);
int[][] jumps = whereKnightCanGo(from);
jumps = checkVisited(jumps, visited);
// check if it reached destination
for(int i = 0; i < jumps.length; i++)
if(jumps[i][0] == to[0] && jumps[i][1] == to[1])
return min;
levelMin[++jumpidx] = jumps.length;
for(int i = 0; i < jumps.length; i++) {
int[] k = {jumps[i][0], jumps[i][1]};
ks.add(k);
}
}
return min;
}
private int[][] addToVisited(int[] from, int[][] visited) {
for(int i = 0; i < visited.length; i++) {
if(visited[i][0] == 0) {
visited[i][0] = from[0];
visited[i][1] = from[1];
break;
}
}
return visited;
}
private int[][] checkVisited(int[][] jumps, int[][] visited) {
int len = jumps.length;
int[][] temp = new int[len][2];
j:for(int i = 0, t = 0; i < jumps.length; i++) {
for(int v = 0; v < visited.length; v++) {
if(jumps[i][0] == visited[v][0] && jumps[i][1] == visited[v][1]) {
len--;
continue j;
}
}
temp[t][0] = jumps[i][0];
temp[t][1] = jumps[i][1];
t++;
}
if(len == jumps.length) return jumps;
int[][] ret = new int[len][2];
for(int i = 0; i < len; i++) {
ret[i][0] = temp[i][0]; ret[i][1] = temp[i][1];
}
return ret;
}
public int[][] whereKnightCanGo(int[] k) {
int len = 8;
int[][] temp = new int[8][2];
// left bottom
temp[0][0] = k[0] - 1;
temp[0][1] = k[1] - 2;
temp[1][0] = k[0] - 2;
temp[1][1] = k[1] - 1;
// right bottom
temp[2][0] = k[0] + 1;
temp[2][1] = k[1] - 2;
temp[3][0] = k[0] + 2;
temp[3][1] = k[1] - 1;
// left top
temp[4][0] = k[0] - 2;
temp[4][1] = k[1] + 1;
temp[5][0] = k[0] - 1;
temp[5][1] = k[1] + 2;
// right top
temp[6][0] = k[0] + 1;
temp[6][1] = k[1] + 2;
temp[7][0] = k[0] + 2;
temp[7][1] = k[1] + 1;
for(int i = 0; i < 8; i++)
if(temp[i][0] < 1 || temp[i][1] < 1) len--;
int[][] ret = new int[len][2];
for(int i = 0, r = 0; i < 8; i++)
if(temp[i][0] > 0 && temp[i][1] > 0) {
ret[r][0] = temp[i][0];
ret[r][1] = temp[i][1];
r++;
}
return ret;
}
/**
* (int)'a' -> 97
* (int)'1' -> 49
*/
public int[] strToIntArray(String s) {
char[] temp = s.toCharArray();
return new int[]{(int)temp[0]-96, (int)temp[1]-48};
}
}
