NEERC/garbling/garbling_gk.java

   1 import java.util.*;
   2 import java.io.*;
   3
   4 public class garbling_gk {
   5     static Scanner in;
   6     static PrintWriter out;
   7
   8     int r;
   9     int c;
  10     int turns = 0;
  11
  12     class Permutation {
  13         final int[] perm;
  14         final long[] times;
  15
  16         Permutation(int[] perm, long[] times) {
  17                 this.perm = perm;
  18                 this.times = times;
  19         }
  20
  21                 public Permutation multiply(Permutation that) {
  22                         int n = perm.length;
  23                         int[] perm = new int[n];
  24                         long[] times = new long[n];
  25
  26                         for (int i = 0; i < n; i++) {
  27                                 int j = this.perm[i];
  28                                 times[i] = this.times[i] + that.times[j];
  29                                 perm[i] = that.perm[j];
  30                         }
  31
  32                         return new Permutation(perm, times);
  33                 }
  34     }
  35
  36         private void garbleLeft(int[][] f, int i, int j) {
  37                 int t = f[i][j];
  38                 f[i][j] = f[i][j + 1];
  39                 f[i][j + 1] = f[i + 1][j + 1];
  40                 f[i + 1][j + 1] = f[i + 1][j];
  41                 f[i + 1][j] = t;
  42         }
  43
  44         private void garbleRight(int[][] f, int i, int j) {
  45                 int t = f[i][j];
  46                 f[i][j] = f[i + 1][j];
  47                 f[i + 1][j] = f[i + 1][j + 1];
  48                 f[i + 1][j + 1] = f[i][j + 1];
  49                 f[i][j + 1] = t;
  50         }
  51
  52         private int[][] fill() {
  53                 int[][] f = new int[r][c];
  54         for (int i = 0; i < r; i++) {
  55                 for (int j = 0; j < c; j++) {
  56                         f[i][j] = index(i, j);
  57                 }
  58         }
  59                 return f;
  60         }
  61
  62         private long[] garble(long n, char[][] g, int[][] f) {
  63                 long[] times = new long[r * c];
  64                 for (int i = 0; i < r - 1; i++) {
  65                 for (int j = 0; j < c - 1; j++) {
  66                         if (n-- == 0) {
  67                                 return times;
  68                         }
  69                         times[f[i][j]]++;
  70                         if (g[i][j] == 'L') {
  71                                 garbleLeft(f, i, j);
  72                         } else if (g[i][j] == 'R') {
  73                                 garbleRight(f, i, j);
  74                         }
  75                 }
  76         }
  77                 assert n == 0;
  78                 return times;
  79         }
  80
  81         private Permutation garble(long n, char[][] g) {
  82                 int[][] f = fill();
  83
  84                 long[] times = garble(n, g, f);
  85                 int[] perm = new int[r * c];
  86                 for (int i = 0; i < r; i++) {
  87                         for (int j = 0; j < c; j++) {
  88                                 perm[f[i][j]] = index(i, j);
  89                         }
  90                 }
  91                 return new Permutation(perm, times);
  92         }
  93
  94         private int index(int i, int j) {
  95                 return i * c + j;
  96         }
  97
  98     public void run() {
  99         r = in.nextInt();
 100         c = in.nextInt();
 101         long n = in.nextLong();
 102
 103         char[][] g = new char[r - 1][];
 104         for (int i = 0; i < r - 1; i++) {
 105                 g[i] = in.next().toCharArray();
 106         }
 107
 108         int loop = (r - 1) * (c - 1);
 109                 Permutation result = garble(n % loop, g);
 110         Permutation power = garble(loop, g);
 111         long q = n / loop;
 112         while (q != 0) {
 113                 if (q % 2 == 1) {
 114                         result = power.multiply(result);
 115                 }
 116                 power = power.multiply(power);
 117                 q /= 2;
 118         }
 119
 120         for (int i = 0; i < r; i++) {
 121                 for (int j = 0; j < c; j++) {
 122                         out.println(result.times[index(i, j)]);
 123                 }
 124         }
 125     }
 126
 127     public static void main(String[] args) throws Exception {
 128         in = new Scanner(new File("garbling.in"));
 129         out = new PrintWriter("garbling.out");
 130
 131         new garbling_gk().run();
 132
 133         in.close();
 134         out.close();
 135     }
 136 }