// CCC 1998 // Problem E: MountianPassage // Can't go up or down more than 2 units, if either location > top left // corner, oxygen is reguired. // this is a dynamic programmming type problem: // starting at top corner, create a list of all points visited (the top one) // got thru the list and update a distance array (a 2D array) // (the distance is the same as current or 1 more, provided you can reach it.) // create a new list of all the newly changed points. // continue until the list is empty. // eg: if you had // 2 3 4 // 4 6 9 // 6 9 5 // // the list (x) would be (0,0) // distance array would be: // 0 9999 9999 // 9999 9999 9999 // 9999 9999 9999 // then the new list (y) would be (0,1) and (1,0) // distance array would be: // 0 1 9999 // 1 9999 9999 // 9999 9999 9999 // copy y into x // then the new list (y) would be (0,2), (1,1) and (2,0) // distance array would be: // 0 1 2 // 1 2 9999 // 2 9999 9999 // copy y into x // then the new list (y) would be null // can't go any further // BUT if you could, reading the bottom right element gives the answer. // file input and output. // input: number of trips, then size of square and the then the square itself // output: the # of oxygen units used. import java.awt.*; import hsa.*; public class P5MountianPassage { static Console cc; public static void main (String [] args) { cc = new Console (); TextInputFile fi = new TextInputFile ("passage.in"); TextOutputFile fo = new TextOutputFile ("passage.out"); int n, oxy; int [] [] g; int size; n = fi.readInt (); for (int i = 1 ; i <= n ; i++) { // read the size, // create the main grid (g) and distance (d) 2D arrays size = fi.readInt (); g = new int [size] [size]; int [] [] d = new int [size] [size]; for (int r = 0 ; r < size ; r++) for (int c = 0 ; c < size ; c++) { g [r] [c] = fi.readInt (); d [r] [c] = 9999; } // create the old (x) and new(y) lists of points Point [] x = new Point [625]; Point [] y = new Point [625]; for (int j = 0 ; j < 625 ; j++) { x [j] = new Point (); y [j] = new Point (); } // set oxygen limit and initialize list (x) and d oxy = g [0] [0]; x [0].r = 0; x [0].c = 0; d [0] [0] = 0; int k = 1; // size of old list (x) int h; do { // t is the size of the new list (y) int t = 0; for (int j = 0 ; j < k ; j++) { int a = x [j].r; int b = x [j].c; // go up if you can if (a - 1 >= 0 && d [a - 1] [b] > d [a] [b] && Math.abs (g [a - 1] [b] - g [a] [b]) <= 2) { h = d [a - 1] [b]; if (g [a - 1] [b] > oxy || g [a] [b] > oxy) d [a - 1] [b] = d [a] [b] + 1; else d [a - 1] [b] = d [a] [b]; if (d [a - 1] [b] < h) { y [t].r = a - 1; y [t].c = b; t++; } } // go left if you can if (b - 1 >= 0 && d [a] [b - 1] > d [a] [b] && Math.abs (g [a] [b - 1] - g [a] [b]) <= 2) { h = d [a] [b - 1]; if (g [a] [b - 1] > oxy || g [a] [b] > oxy) d [a] [b - 1] = d [a] [b] + 1; else d [a] [b - 1] = d [a] [b]; if (d [a] [b - 1] < h) { y [t].r = a; y [t].c = b - 1; t++; } } // go down if you can if (a + 1 < size && d [a + 1] [b] > d [a] [b] && Math.abs (g [a + 1] [b] - g [a] [b]) <= 2) { h = d [a + 1] [b]; if (g [a + 1] [b] > oxy || g [a] [b] > oxy) d [a + 1] [b] = d [a] [b] + 1; else d [a + 1] [b] = d [a] [b]; if (d [a + 1] [b] < h) { y [t].r = a + 1; y [t].c = b; t++; } } // go right if you can if (b + 1 < size && d [a] [b + 1] > d [a] [b] && Math.abs (g [a] [b + 1] - g [a] [b]) <= 2) { h = d [a] [b + 1]; if (g [a] [b + 1] > oxy || g [a] [b] > oxy) d [a] [b + 1] = d [a] [b] + 1; else d [a] [b + 1] = d [a] [b]; if (d [a] [b + 1] < h) { y [t].r = a; y [t].c = b + 1; t++; } } } // move new (y) into old (x) list for (int j = 0 ; j < t ; j++) { x [j].r = y [j].r; x [j].c = y [j].c; } k = t; } while (k > 0); // the answer is in the bottom right of distance array if (d [size - 1] [size - 1] == 9999) { fo.println ("CANNOT MAKE TRIP"); cc.println ("CANNOT MAKE TRIP"); } else { fo.println (d [size - 1] [size - 1]); cc.println (d [size - 1] [size - 1]); } fo.println (); } } } class Point { public int r, c; }