daily pastebin goal
4%
SHARE
TWEET

Untitled

a guest Apr 25th, 2018 48 Never
Upgrade to PRO!
ENDING IN00days00hours00mins00secs
 
  1. import static java.util.Arrays.fill;
  2.  
  3. import java.io.*;
  4. import java.util.*;
  5.  
  6. public class chess_nn {
  7.  
  8.     static final String COLORS = "WB";
  9.     static final int MAXN = 100;
  10.  
  11.     public static void main(String[] args) throws FileNotFoundException {
  12.         Scanner in = new Scanner(new File("chess.in"));
  13.         int n = in.nextInt();
  14.         int m = in.nextInt();
  15.         assert(1 <= n && n <= MAXN);
  16.         assert(1 <= m && m <= MAXN);
  17.         char[][] c = new char[n][m];
  18.         for (int i = 0; i < n; i++) {
  19.             c[i] = in.next().toCharArray();
  20.             assert(c[i].length == m);
  21.             for (int j = 0; j < m; j++) {
  22.                 assert(COLORS.indexOf(c[i][j]) >= 0);
  23.             }
  24.         }
  25.         Answer best = null;
  26.         for (int color = 0; color < 2; color++) {
  27.             Answer ans = solve(color, n, m, c);
  28.             if (best == null || ans.count < best.count) {
  29.                 best = ans;
  30.             }
  31.         }
  32.         PrintWriter out = new PrintWriter("chess.out");
  33.         out.println(best.count);
  34.         for (String e : best.answers) {
  35.             out.println(e);
  36.         }
  37.         out.close();
  38.     }
  39.  
  40.     static Answer solve(int color, int n, int m, char[][] c) {
  41.         int[] p1 = new int[n + m - 1];
  42.         int[] p2 = new int[n + m - 1];
  43.         fill(p1, -1);
  44.         fill(p2, -1);
  45.         boolean[] was = new boolean[n + m - 1];
  46.         int ans = 0;
  47.         for (int i = 0; i < n + m - 1; i++) {
  48.             fill(was, false);
  49.             if (dfs(i, c, color, p1, p2, was)) {
  50.                 ++ans;
  51.             }
  52.         }
  53.         String[] answer = new String[ans];
  54.         fill(was, false);
  55.         for (int i = 0; i < n + m - 1; i++) {
  56.             if (p1[i] < 0) {
  57.                 dfs(i, c, color, p1, p2, was);
  58.             }
  59.         }
  60.         int count = 0;
  61.         for (int i = 0; i < n + m - 1; i++) {
  62.             if (p1[i] >= 0 && !was[i]) {
  63.                 answer[count++] = getDiagonal1(i, n, m, color);
  64.             }
  65.         }
  66.         for (int j = 0; j < n + m - 1; j++) {
  67.             if (p2[j] >= 0 && was[p2[j]]) {
  68.                 answer[count++] = getDiagonal2(j, n, m, color);
  69.             }
  70.         }
  71.         for (int i = 0; i < n + m - 1; i++) {
  72.             for (int j = 0; j < n + m - 1; j++) {
  73.                 if (!hasEdge(i, j, c, color)) {
  74.                     continue;
  75.                 }
  76.                 if (p1[i] >= 0 && !was[i] || p2[j] >= 0 && was[p2[j]]) {
  77.                    
  78.                 } else {
  79.                     throw new AssertionError();
  80.                 }
  81.             }
  82.         }
  83.         return new Answer(ans, answer);
  84.     }
  85.  
  86.     static String getDiagonal1(int sum, int n, int m, int color) {
  87.         int x = Math.min(sum, n - 1);
  88.         int y = sum - x;
  89.         return "1 " + (x + 1) + " " + (y + 1) + " "
  90.                 + COLORS.charAt((color ^ x ^ y) & 1);
  91.     }
  92.  
  93.     static String getDiagonal2(int dif, int n, int m, int color) {
  94.         dif -= m - 1;
  95.         int x = Math.max(dif, 0);
  96.         int y = x - dif;
  97.         return "2 " + (x + 1) + " " + (y + 1) + " "
  98.                 + COLORS.charAt((color ^ x ^ y) & 1);
  99.     }
  100.  
  101.     static boolean hasEdge(int sum, int dif, char[][] c, int color) {
  102.         dif -= c[0].length - 1;
  103.         if ((sum & 1) != (dif & 1)) {
  104.             return false;
  105.         }
  106.         int x = (sum + dif) / 2;
  107.         int y = (sum - dif) / 2;
  108.         if (x < 0 || x >= c.length || y < 0 || y >= c[x].length) {
  109.             return false;
  110.         }
  111.         return COLORS.indexOf(c[x][y]) != ((x ^ y ^ color) & 1);
  112.     }
  113.  
  114.     static boolean dfs(int v, char[][] c, int color, int[] p1, int[] p2,
  115.             boolean[] was) {
  116.         if (was[v]) {
  117.             return false;
  118.         }
  119.         was[v] = true;
  120.         for (int i = 0; i < c.length + c[0].length; i++) {
  121.             if (!hasEdge(v, i, c, color)) {
  122.                 continue;
  123.             }
  124.             if (p2[i] < 0 || dfs(p2[i], c, color, p1, p2, was)) {
  125.                 p2[i] = v;
  126.                 p1[v] = i;
  127.                 return true;
  128.             }
  129.         }
  130.         return false;
  131.     }
  132.  
  133.     static class Answer {
  134.         int count;
  135.         String[] answers;
  136.  
  137.         public Answer(int count, String[] answers) {
  138.             this.count = count;
  139.             this.answers = answers;
  140.         }
  141.  
  142.     }
  143. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top