// Solution to "Pushing Boxes" by Bob Roos import java.io.*; import java.util.*; public class Pushing { public static int ht, wd; // height and width of room public static int n; // number of boxes in room public static int row[], col[]; // locations of boxes public static int rowcount[], colcount[]; // number of boxes in each row,col public static int room[][] = new int[20][20]; public static int maxrowcount, maxcolcount; // largest number of boxes in // any row or col public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; String line; int count = 0; while ((line = in.readLine()) != null) { st = new StringTokenizer(line); ht = Integer.parseInt(st.nextToken()); wd = Integer.parseInt(st.nextToken()); if (ht == 0 && wd == 0) break; count++; line = in.readLine(); st = new StringTokenizer(line); n = Integer.parseInt(st.nextToken()); row = new int[n]; rowcount = new int[20]; col = new int[n]; colcount = new int[20]; maxrowcount = maxcolcount = 0; emptyRoom(); for (int i = 0; i < n; i++) { row[i] = Integer.parseInt(st.nextToken()); col[i] = Integer.parseInt(st.nextToken()); room[row[i]][col[i]] = 1; rowcount[row[i]]++; colcount[col[i]]++; } // display(); process(in); System.out.print("Data set " + count + " ends with boxes at locations"); for (int row = 0; row < ht; row++) { for (int col = 0; col < wd; col++) { if (room[row][col] > 0) System.out.print(" (" + row + "," + col + ")"); } } System.out.println("."); } } public static void process(BufferedReader in) throws IOException { String line; StringTokenizer st; while ((line = in.readLine()) != null) { st = new StringTokenizer(line); String cmd = st.nextToken(); if (cmd.equals("done")) break; else if (cmd.equals("up")) { int dist = Integer.parseInt(st.nextToken()); move(dist,"u"); } else if (cmd.equals("down")) { int dist = Integer.parseInt(st.nextToken()); move(dist,"d"); } else if (cmd.equals("left")) { int dist = Integer.parseInt(st.nextToken()); move(dist,"l"); } else if (cmd.equals("right")) { int dist = Integer.parseInt(st.nextToken()); move(dist,"r"); } else { System.out.println("This shouldn't be happening" + cmd); } } } // Move a wall a given amount "amt" in direction "dir" public static void move(int amt, String dir) { findMax(); // find maximum number of boxes in any row and any col if (dir.equals("l")) { amt = Math.min(amt,wd-maxrowcount); // can't move wall further than // largest # of boxes in any row for (int col = wd-1; col >= wd-amt; col--) { for (int row = 0; row < ht; row++) { if (room[row][col] > 0) { room[row][col] = 0; int j = col-1; while (room[row][j] > 0) j--; room[row][j] = 1; } } } } else if (dir.equals("r")) { amt = Math.min(amt,wd-maxrowcount); // can't move wall further than // largest # of boxes in any row for (int col = 0; col < amt; col++) { for (int row = 0; row < ht; row++) { if (room[row][col] > 0) { room[row][col] = 0; int j = col+1; while (room[row][j] > 0) j++; room[row][j] = 1; } } } } else if (dir.equals("u")) { amt = Math.min(amt,ht-maxcolcount); // can't move wall further than // largest # of boxes in any col for (int row = ht-1; row >= ht-amt; row--) { for (int col = 0; col < wd; col++) { if (room[row][col] > 0) { room[row][col] = 0; int i = row-1; while (room[i][col] > 0) i--; room[i][col] = 1; } } } } else { // dir.equals("d") amt = Math.min(amt,ht-maxcolcount); // can't move wall further than // largest # of boxes in any col for (int row = 0; row < amt; row++) { for (int col = 0; col < wd; col++) { if (room[row][col] > 0) { room[row][col] = 0; int i = row+1; while (room[i][col] > 0) i++; room[i][col] = 1; } } } } } // Find maximum number of boxes in any row and any column: public static void findMax() { for (int i = 0; i < wd; i++) colcount[i] = 0; for (int i = 0; i < ht; i++) rowcount[i] = 0; maxcolcount = maxrowcount = 0; for (int row = 0; row < ht; row++) { for (int col = 0; col < wd; col++) { if (room[row][col] > 0) { rowcount[row]++; colcount[col]++; maxrowcount = Math.max(maxrowcount,rowcount[row]); maxcolcount = Math.max(maxcolcount,colcount[col]); } } } } // Set all locations to empty: public static void emptyRoom() { for (int i = 0; i < 20; i++) for (int j = 0; j < 20; j++) room[i][j] = 0; } // Print out locations of boxes: public static void display() { for (int i = 0; i < ht; i++) { for (int j = 0; j < wd; j++) System.out.print(room[i][j]+ " "); System.out.println(); } } }