NEERC/garbling/garbling_mb.java

   1 import java.io.FileReader;
   2 import java.io.IOException;
   3 import java.io.PrintWriter;
   4 import java.util.ArrayList;
   5 import java.util.Scanner;
   6
   7 public class garbling_mb implements Runnable {
   8     private Scanner in;
   9     private PrintWriter out;
  10     private char[][] map;
  11     private int[][] table;
  12     private int numRows;
  13     private int numCols;
  14
  15     public static void main(String[] args) {
  16         new Thread(new garbling_mb()).start();
  17     }
  18
  19     public void run() {
  20         try {
  21             in = new Scanner(new FileReader("garbling.in"));
  22             out = new PrintWriter("garbling.out");
  23
  24             solve();
  25
  26             in.close();
  27             out.close();
  28         } catch (IOException e) {
  29             e.printStackTrace();
  30         }
  31     }
  32
  33     private void rotateClockwise(int row, int col) {
  34         int a = table[row][col];
  35         int b = table[row][col + 1];
  36         int c = table[row + 1][col];
  37         int d = table[row + 1][col + 1];
  38         table[row][col] = c;
  39         table[row][col + 1] = a;
  40         table[row + 1][col] = d;
  41         table[row + 1][col + 1] = b;
  42     }
  43
  44     private void rotateCounterclockwise(int row, int col) {
  45         int a = table[row][col];
  46         int b = table[row][col + 1];
  47         int c = table[row + 1][col];
  48         int d = table[row + 1][col + 1];
  49         table[row][col] = b;
  50         table[row][col + 1] = d;
  51         table[row + 1][col] = a;
  52         table[row + 1][col + 1] = c;
  53     }
  54
  55     private void applyMap(int row, int col) {
  56         if (map[row][col] == 'R') {
  57             rotateClockwise(row, col);
  58         } else if (map[row][col] == 'L') {
  59             rotateCounterclockwise(row, col);
  60         }
  61     }
  62
  63     private void solve() {
  64         numRows = in.nextInt();
  65         numCols = in.nextInt();
  66         long numMoves = in.nextLong();
  67         in.nextLine();
  68
  69         map = new char[numRows - 1][];
  70         for (int row = 0; row < numRows - 1; row++) {
  71             map[row] = new char[numCols - 1];
  72             final String line = in.nextLine();
  73             for (int col = 0; col < numCols - 1; col++) {
  74                 map[row][col] = line.charAt(col);
  75             }
  76         }
  77
  78         initTable();
  79
  80         final long turnLength = (numRows - 1) * (numCols - 1);
  81         final long numTurns = numMoves / turnLength;
  82         final int remMoves = (int) (numMoves % turnLength);
  83
  84         long[] cycleDeltas = new long[numRows * numCols];
  85         simulate(turnLength, cycleDeltas);
  86 //        dumpTable();
  87
  88         long[] counters = new long[numRows * numCols];
  89         boolean[] used = new boolean[numRows * numCols];
  90         for (int i = 0; i < numRows * numCols; i++) {
  91             if (!used[i]) {
  92                 final ArrayList<Integer> permCycle = new ArrayList<Integer>();
  93                 int j = i;
  94                 do {
  95                     permCycle.add(j);
  96                     used[j] = true;
  97                     j = table[j / numCols][j % numCols];
  98                 } while (j != i);
  99
 100                 for (int k = 0; k < permCycle.size(); k++) {
 101                     final int from = permCycle.get(k);
 102                     final int to = permCycle.get((int) ((k + numTurns) % permCycle.size()));
 103                     table[from / numCols][from % numCols] = to;
 104                 }
 105
 106                 long totalDelta = 0;
 107                 for (int value : permCycle) {
 108                     totalDelta += cycleDeltas[value];
 109                 }
 110
 111                 final long numCycles = numTurns / permCycle.size();
 112                 for (int value: permCycle) {
 113                     counters[value] += totalDelta * numCycles;
 114                 }
 115
 116                 final int remCycles = (int) (numTurns % permCycle.size());
 117                 for (int k = 0; k < remCycles; k++) {
 118                     for (int l = 0; l < permCycle.size(); l++) {
 119                         final int pos = permCycle.get(((l + k) % permCycle.size()));
 120                         counters[pos] += cycleDeltas[permCycle.get(l)];
 121                     }
 122                 }
 123             }
 124         }
 125
 126 //        dumpTable();
 127         simulate(remMoves, counters);
 128
 129         for (long value : counters) {
 130             out.println(value);
 131         }
 132     }
 133
 134     private void simulate(long numMoves, long[] counters) {
 135         int row = 0;
 136         int col = 0;
 137         for (int i = 0; i < numMoves; i++) {
 138             counters[table[row][col]]++;
 139             applyMap(row, col);
 140             col++;
 141             if (col == numCols - 1) {
 142                 row++;
 143                 col = 0;
 144             }
 145             if (row == numRows - 1) {
 146                 row = 0;
 147             }
 148         }
 149     }
 150
 151     private void initTable() {
 152         table = new int[numRows][];
 153         int counter = 0;
 154         for (int row = 0; row < numRows; row++) {
 155             table[row] = new int[numCols];
 156             for (int col = 0; col < numCols; col++) {
 157                 table[row][col] = counter++;
 158             }
 159         }
 160     }
 161
 162     private void dumpTable() {
 163         for (int row = 0; row < numRows; row++) {
 164             for (int col = 0; col < numCols; col++) {
 165                 System.out.printf("%3d ", table[row][col]);
 166             }
 167             System.out.println();
 168         }
 169     }
 170
 171 }