Назад к лучшим решениям Status: AC, problem ZSUD, contest ZEL07. By klopyrev (Konstantin Lopyrev), 2007-02-20 00:30:53.
  1. import java.io.*;
  2. public class Main
  3. {
  4.     private static int[] maze;
  5.     private static boolean found;
  6.     private static boolean[] [] col;
  7.     private static boolean[] [] row;
  8.     private static boolean[] [] box;
  9.     private static boolean[] empty;
  10.     private static final int[] c = {0, 1, 2, 3, 4, 5, 6, 7, 8, 0, 1, 2, 3, 4, 5, 6, 7, 8, 0, 1, 2, 3, 4, 5, 6, 7, 8, 0, 1, 2, 3, 4, 5, 6, 7, 8, 0, 1, 2, 3, 4, 5, 6, 7, 8, 0, 1, 2, 3, 4, 5, 6, 7, 8, 0, 1, 2, 3, 4, 5, 6, 7, 8, 0, 1, 2, 3, 4, 5, 6, 7, 8, 0, 1, 2, 3, 4, 5, 6, 7, 8};
  11.     private static final int[] r = {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8};
  12.     private static final int[] b = {0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 3, 3, 3, 4, 4, 4, 5, 5, 5, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8, 6, 6, 6, 7, 7, 7, 8, 8, 8, 6, 6, 6, 7, 7, 7, 8, 8, 8};
  13.     private static long time;
  14.     public static void solve (int cur)
  15.     {
  16.         if (cur == maze.length)
  17.         {
  18.             found = true;
  19.             return;
  20.         }
  21.         if (!empty [cur])
  22.         {
  23.             solve (cur + 1);
  24.             return;
  25.         }
  26.         for (int i = 1 ; i <= 9 && !found ; i++)
  27.         {
  28.             if (!row [r [cur]] [i - 1] && !col [c [cur]] [i - 1] && !box [b [cur]] [i - 1])
  29.             {
  30.                 row [r [cur]] [i - 1] = true;
  31.                 col [c [cur]] [i - 1] = true;
  32.                 box [b [cur]] [i - 1] = true;
  33.                 maze [cur] = i;
  34.                 solve (cur + 1);
  35.                 row [r [cur]] [i - 1] = false;
  36.                 col [c [cur]] [i - 1] = false;
  37.                 box [b [cur]] [i - 1] = false;
  38.             }
  39.         }
  40.     }
  41.  
  42.  
  43.     public static void main (String[] args) throws IOException
  44.     {
  45.         time = System.currentTimeMillis ();
  46.         BufferedReader in = new BufferedReader (new InputStreamReader (System.in));
  47.         int T = Integer.parseInt (in.readLine ());
  48.         for (int cases = 0 ; cases < T ; cases++)
  49.         {
  50.             char[] temp = in.readLine ().toCharArray ();
  51.             col = new boolean [9] [9];
  52.             row = new boolean [9] [9];
  53.             box = new boolean [9] [9];
  54.             maze = new int [temp.length];
  55.             empty = new boolean [temp.length];
  56.             int unfilled = 0;
  57.             for (int i = 0 ; i < maze.length ; i++)
  58.             {
  59.                 if (temp [i] != '.')
  60.                 {
  61.                     maze [i] = temp [i] - '0';
  62.                     col [c [i]] [maze [i] - 1] = true;
  63.                     row [r [i]] [maze [i] - 1] = true;
  64.                     box [b [i]] [maze [i] - 1] = true;
  65.                 }
  66.                 else
  67.                 {
  68.                     maze [i] = 0;
  69.                     empty [i] = true;
  70.                     unfilled++;
  71.                 }
  72.             }
  73.             boolean change = true;
  74.             while (unfilled != 0 && change)
  75.             {
  76.                 change = false;
  77.                 int[] [] placeRows = new int [9] [9];
  78.                 int[] [] rowLoc = new int [9] [9];
  79.                 int[] [] placeCols = new int [9] [9];
  80.                 int[] [] colLoc = new int [9] [9];
  81.                 int[] [] placeBoxes = new int [9] [9];
  82.                 int[] [] boxA = new int [9] [9];
  83.                 int[] [] boxB = new int [9] [9];
  84.                 for (int i = 0 ; i < 81 ; i++)
  85.                 {
  86.                     if (empty [i])
  87.                     {
  88.                         int number = -1;
  89.                         boolean valid = true;
  90.                         for (int j = 1 ; j <= 9 ; j++)
  91.                         {
  92.                             if (!row [r [i]] [j - 1] && !col [c [i]] [j - 1] && !box [b [i]] [j - 1])
  93.                             {
  94.                                 placeRows [r [i]] [j - 1]++;
  95.                                 rowLoc [r [i]] [j - 1] = c [i];
  96.                                 placeCols [c [i]] [j - 1]++;
  97.                                 colLoc [c [i]] [j - 1] = r [i];
  98.                                 placeBoxes [b [i]] [j - 1]++;
  99.                                 boxA [b [i]] [j - 1] = r [i];
  100.                                 boxB [b [i]] [j - 1] = c [i];
  101.                                 if (number == -1)
  102.                                     number = j;
  103.                                 else
  104.                                     valid = false;
  105.                             }
  106.                         }
  107.                         if (valid)
  108.                         {
  109.                             row [r [i]] [number - 1] = true;
  110.                             col [c [i]] [number - 1] = true;
  111.                             box [b [i]] [number - 1] = true;
  112.                             maze [i] = number;
  113.                             empty [i] = false;
  114.                             change = true;
  115.                             unfilled--;
  116.                         }
  117.                     }
  118.                 }
  119.                 if (unfilled != 0)
  120.                 {
  121.                     for (int i = 0 ; i < 9 ; i++)
  122.                     {
  123.                         for (int j = 0 ; j < 9 ; j++)
  124.                         {
  125.                             if (placeRows [i] [j] == 1)
  126.                             {
  127.                                 boolean done = false;
  128.                                 int cols = rowLoc [i] [j];
  129.                                 int place = i * 9 + cols;
  130.                                 if (!row [r [place]] [j] && !col [c [place]] [j] && !box [b [place]] [j] && empty [place])
  131.                                 {
  132.                                     done = true;
  133.                                     row [r [place]] [j] = true;
  134.                                     col [c [place]] [j] = true;
  135.                                     box [b [place]] [j] = true;
  136.                                     maze [place] = j + 1;
  137.                                     change = true;
  138.                                     empty [place] = false;
  139.                                     unfilled--;
  140.                                 }
  141.                             }
  142.                         }
  143.                     }
  144.                 }
  145.                 if (unfilled != 0)
  146.                 {
  147.                     for (int i = 0 ; i < 9 ; i++)
  148.                     {
  149.                         for (int j = 0 ; j < 9 ; j++)
  150.                         {
  151.                             if (placeCols [i] [j] == 1)
  152.                             {
  153.                                 boolean done = false;
  154.                                 int rows = colLoc [i] [j];
  155.                                 int place = rows * 9 + i;
  156.                                 if (!row [r [place]] [j] && !col [c [place]] [j] && !box [b [place]] [j] && empty [place])
  157.                                 {
  158.                                     done = true;
  159.                                     row [r [place]] [j] = true;
  160.                                     col [c [place]] [j] = true;
  161.                                     box [b [place]] [j] = true;
  162.                                     maze [place] = j + 1;
  163.                                     change = true;
  164.                                     empty [place] = false;
  165.                                     unfilled--;
  166.                                 }
  167.                             }
  168.                         }
  169.                     }
  170.                 }
  171.                 if (unfilled != 0)
  172.                 {
  173.                     for (int i = 0 ; i < 9 ; i++)
  174.                     {
  175.                         for (int j = 0 ; j < 9 ; j++)
  176.                         {
  177.                             if (placeBoxes [i] [j] == 1)
  178.                             {
  179.  
  180.                                 boolean done = false;
  181.                                 int rows = boxA [i] [j];
  182.                                 int cols = boxB [i] [j];
  183.                                 int place = rows * 9 + cols;
  184.                                 if (!row [r [place]] [j] && !col [c [place]] [j] && !box [b [place]] [j] && empty [place])
  185.                                 {
  186.                                     done = true;
  187.                                     row [r [place]] [j] = true;
  188.                                     col [c [place]] [j] = true;
  189.                                     box [b [place]] [j] = true;
  190.                                     maze [place] = j + 1;
  191.                                     change = true;
  192.                                     empty [place] = false;
  193.                                     unfilled--;
  194.                                 }
  195.                             }
  196.                         }
  197.                     }
  198.                 }
  199.             }
  200.             found = false;
  201.             if (unfilled == 0)
  202.                 found = true;
  203.             if (!found)
  204.                 solve (0);
  205.             System.out.println ("Y");
  206.             String output = "";
  207.             for (int i = 0 ; i < maze.length ; i++)
  208.                 output += maze [i];
  209.             System.out.println (output);
  210.  
  211.         }
  212.     }
  213. }
  214.  
  215.  
  216.