fork download
copy 
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.*;
  5.  
  6. class Rextester {
  7.     List<Set<String>> words;
  8.     int[][] counts;
  9.  
  10. //try to run with the following input:
  11. //1
  12. //6 6 2
  13. //++++++
  14. //+____+
  15. //++++_+
  16. //++++_+
  17. //++++_+
  18. //++++++
  19. //pain
  20. //nice
  21. //    
  22.  
  23.     public static void main(String[] args) throws IOException {
  24.         Rextester r = new Rextester();
  25.         r.run();
  26.     }
  27.  
  28.     public void run() throws IOException {
  29.         InputStreamReader r = new InputStreamReader(System.in);
  30.         BufferedReader in = new BufferedReader(r);
  31.         String line = in.readLine();
  32.         int t = Integer.parseInt(line);
  33.         for (int k = 1; k <= t; k++) {
  34.             line = in.readLine();
  35.             String[] parts = line.split(" ");
  36.             int x = Integer.parseInt(parts[0]);
  37.             int y = Integer.parseInt(parts[1]);
  38.             int amount = Integer.parseInt(parts[2]);
  39.  
  40.             char[][] c = new char[y+2][x+2];
  41.             for (int i = 1; i <= y; i++) {
  42.                 line = "+" + in.readLine() + "+";
  43.                 c[i] = line.toCharArray();
  44.             }
  45.             for (int i = 0; i <= x+1; i++) {
  46.                 c[0][i] = '+';
  47.                 c[y+1][i] = '+';
  48.             }
  49.  
  50.             words = new ArrayList<>();
  51.             counts = new int[y+2][x+2];
  52.             for (int i = 2; i <= 250; i++)
  53.                 words.add(new HashSet<String>());
  54.             for (int i = 0; i < amount; i++) {
  55.                 line = in.readLine();
  56.                 words.get(line.length()).add(line);
  57.             }
  58.             in.readLine();
  59.  
  60.             Stack<Placeholder> placeholders = new Stack<>();
  61.             for (int i = 1; i <= y; i++)
  62.                 for (int j = 1; j <= x; j++)
  63.                     if (c[i][j-1] == '+' && c[i][j] == '_' && c[i][j+1] == '_') {
  64.                         int xx = j; int ll = 0;
  65.                         while (c[i][j] == '_') {
  66.                             ll++;
  67.                             j++;
  68.                         }
  69.                         placeholders.push(new Placeholder(xx, i, ll, true));
  70.                     }
  71.  
  72.             for (int j = 1; j <= x; j++)
  73.                 for (int i = 1; i <= y; i++)
  74.                     if (c[i-1][j] == '+' && c[i][j] == '_' && c[i+1][j] == '_') {
  75.                         int yy = i; int ll = 0;
  76.                         while (c[i][j] == '_') {
  77.                             ll++;
  78.                             i++;
  79.                         }
  80.                         placeholders.push(new Placeholder(j, yy, ll, false));
  81.                     }
  82.  
  83.             c = solve(c, placeholders);
  84.             System.out.println("Case #" + k + ":");
  85.             for (int i = 1; i <= y; i++) {
  86.                 for (int j = 1; j <= x; j++)
  87.                     System.out.print(c[i][j]);
  88.                 System.out.println();
  89.             }
  90.             if (k!=t)
  91.                 System.out.println();
  92.         }
  93.     }
  94.  
  95.     char[][] solve (char[][] c, Stack<Placeholder> placeholders) {
  96.         if (placeholders.isEmpty())
  97.             return c;
  98.  
  99.         Placeholder pl = placeholders.pop();
  100.         for (String word : words.get(pl.l)) {
  101.             if (fill(c, word, pl)) {
  102.                 char[][] ret = solve(c, placeholders);
  103.                 if (ret != null)
  104.                     return ret;
  105. 	            unfill(c, pl);
  106.             }
  107.         }
  108.         placeholders.push(pl);
  109.         return null;
  110.     }
  111.  
  112.     boolean fill (char[][] c, String word, Placeholder pl) {
  113.         if (pl.h) {
  114.             for (int i = pl.x; i < pl.x + pl.l; i++)
  115.                 if (c[pl.y][i] != '_' && c[pl.y][i] != word.charAt(i - pl.x))
  116.                     return false;
  117.             for (int i = pl.x; i < pl.x + pl.l; i++) {
  118.                 c[pl.y][i] = word.charAt(i - pl.x);
  119.                 counts[pl.y][i]++;
  120.             }
  121.             return true;
  122.  
  123.         } else {
  124.             for (int i = pl.y; i < pl.y + pl.l; i++)
  125.                 if (c[i][pl.x] != '_' && c[i][pl.x] != word.charAt(i - pl.y))
  126.                     return false;
  127.             for (int i = pl.y; i < pl.y + pl.l; i++) {
  128.                 c[i][pl.x] = word.charAt(i - pl.y);
  129.                 counts[i][pl.x]++;
  130.             }
  131.             return true;
  132.         }
  133.     }
  134.  
  135.     void unfill(char[][] c, Placeholder pl) {
  136.         if (pl.h) {
  137.             for (int i = pl.x; i < pl.x + pl.l; i++)
  138.                 if (--counts[pl.y][i] == 0)
  139.                     c[pl.y][i] = '_';
  140.         } else {
  141.             for (int i = pl.y; i < pl.y + pl.l; i++)
  142.                 if (--counts[i][pl.x] == 0)
  143.                     c[i][pl.x] = '_';
  144.         }
  145.     }
  146. }
  147. class Placeholder {
  148.     int x, y, l;
  149.     boolean h;
  150.     public Placeholder(int x, int y, int l, boolean h) {
  151.         this.x = x;
  152.         this.y = y;
  153.         this.l = l;
  154.         this.h = h;
  155.     }
  156. }
  157.  
Success #stdin #stdout 0.04s 4386816KB
comments (?)
stdin
copy 
1
6 6 2
++++++
+____+
++++_+
++++_+
++++_+
++++++
pain
nice
stdout
copy 
Case #1:
++++++
+pain+
++++i+
++++c+
++++e+
++++++
https://ideone.com/o5u5GO
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!