Guest User

jte

a guest
Aug 20th, 2011
415
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5.05 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;
  3. import java.io.PrintWriter;
  4. import java.io.IOException;
  5. import java.lang.reflect.MalformedParameterizedTypeException;
  6. import java.util.ArrayList;
  7. import java.util.Arrays;
  8. import java.util.List;
  9. import java.util.StringTokenizer;
  10.  
  11. public class TaskD extends Thread {
  12.     public TaskD() {
  13.         this.input = new BufferedReader(new InputStreamReader(System.in));
  14.         this.output = new PrintWriter(System.out);
  15.         this.setPriority(Thread.MAX_PRIORITY);
  16.     }
  17.  
  18.     private void solve() throws Throwable {
  19.         int n = nextInt(), m = nextInt();
  20.         char[][] map = new char[n][];
  21.         for (int i = 0; i < n; ++i) {
  22.             map[i] = nextToken().toCharArray();
  23.         }
  24.         List<Integer> X = new ArrayList<Integer>();
  25.         List<Integer> Y = new ArrayList<Integer>();
  26.         StringBuffer result = new StringBuffer();
  27.         int[][] north = new int[n][m];
  28.         int[][] south = new int[n][m];
  29.         int[][] east = new int[n][m];
  30.         int[][] west = new int[n][m];
  31.         int q = nextInt();
  32.         char []dir = new char[q];
  33.         int []len = new int[q];
  34.         for (int i = 0; i < q; ++i) {
  35.             dir[i] = nextToken().charAt(0);
  36.             len[i] = nextInt();
  37.         }
  38.         for (int i = 0; i < n; ++i) {
  39.             if (map[i][m - 1] != '.' && map[i][m - 1] != '#') {
  40.                 X.add(i);
  41.                 Y.add(m - 1);
  42.             }
  43.             for (int j = m - 2; j >= 0; --j) {
  44.                 if (map[i][j + 1] != '#' && map[i][j] != '#') {
  45.                     east[i][j] = east[i][j + 1] + 1;
  46.                 }
  47.                 if (map[i][j] != '.' && map[i][j] != '#') {
  48.                     X.add(i);
  49.                     Y.add(j);
  50.                 }
  51.  
  52.             }
  53.             for (int j = 1; j < m; ++j) {
  54.                 if (map[i][j - 1] != '#' && map[i][j] != '#') {
  55.                     west[i][j] = west[i][j - 1] + 1;
  56.                 }
  57.  
  58.             }
  59.         }
  60.         for (int i = 0; i < m; ++i) {
  61.             for (int j = n - 2; j >= 0; --j) {
  62.                 if (map[j + 1][i] != '#' && map[j][i] != '#') {
  63.                     south[j][i] = south[j + 1][i] + 1;
  64.                 }
  65.             }
  66.             for (int j = 1; j < n; ++j) {
  67.                 if (map[j - 1][i] != '#' && map[j][i] != '#') {
  68.                     north[j][i] = north[j - 1][i] + 1;
  69.                 }
  70.             }
  71.         }
  72.         for (int i = 0; i < X.size(); ++i) {
  73.             int x = X.get(i), y = Y.get(i);
  74.             boolean can = true;
  75.             for (int instr = 0; instr < q && can; ++instr) {
  76.                 switch (dir[instr]) {
  77.                     case 'E':
  78.                         if (east[x][y] >= len[instr]) {
  79.                             y += len[instr];
  80.                         } else {
  81.                             can = false;
  82.                         }
  83.                         break;
  84.                     case 'W':
  85.                         if (west[x][y] >= len[instr]) {
  86.                             y -= len[instr];
  87.                         } else {
  88.                             can = false;
  89.                         }
  90.                         break;
  91.                     case 'N':
  92.                         if (north[x][y] >= len[instr]) {
  93.                             x -= len[instr];
  94.                         } else {
  95.                             can = false;
  96.                         }
  97.                         break;
  98.                     case 'S':
  99.                         if (south[x][y] >= len[instr]) {
  100.                             x += len[instr];
  101.                         } else {
  102.                             can = false;
  103.                         }
  104.                         break;
  105.                 }
  106.             }
  107.             if (can) {
  108.                 result.append(map[X.get(i)][Y.get(i)]);
  109.             }
  110.         }
  111.         char []answer = result.toString().toCharArray();
  112.         Arrays.sort(answer);
  113.         if (answer.length == 0) {
  114.             output.println("no solution");
  115.         } else {
  116.             for (char current : answer) {
  117.                 output.print(current);
  118.             }
  119.             output.println();
  120.         }
  121.  
  122.     }
  123.  
  124.     public void run() {
  125.         try {
  126.             solve();
  127.         } catch (Throwable e) {
  128.             System.err.println(e.getMessage());
  129.             e.printStackTrace();
  130.             System.exit(666);
  131.         } finally {
  132.             output.flush();
  133.             output.close();
  134.         }
  135.     }
  136.  
  137.     public static void main(String[] args) {
  138.         new TaskD().start();
  139.     }
  140.  
  141.     private int nextInt() throws IOException {
  142.         return Integer.parseInt(nextToken());
  143.     }
  144.  
  145.     private long nextLong() throws IOException {
  146.         return Long.parseLong(nextToken());
  147.     }
  148.  
  149.     private double nextDouble() throws IOException {
  150.         return Double.parseDouble(nextToken());
  151.     }
  152.  
  153.     private String nextToken() throws IOException {
  154.         while (tokens == null || !tokens.hasMoreTokens()) {
  155.             tokens = new StringTokenizer(input.readLine());
  156.         }
  157.         return tokens.nextToken();
  158.     }
  159.  
  160.     private BufferedReader input;
  161.     private PrintWriter output;
  162.     private StringTokenizer tokens = null;
  163. }
Advertisement
Add Comment
Please, Sign In to add comment