Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader;
- import java.io.InputStreamReader;
- import java.io.PrintWriter;
- import java.io.IOException;
- import java.lang.reflect.MalformedParameterizedTypeException;
- import java.util.ArrayList;
- import java.util.Arrays;
- import java.util.List;
- import java.util.StringTokenizer;
- public class TaskD extends Thread {
- public TaskD() {
- this.input = new BufferedReader(new InputStreamReader(System.in));
- this.output = new PrintWriter(System.out);
- this.setPriority(Thread.MAX_PRIORITY);
- }
- private void solve() throws Throwable {
- int n = nextInt(), m = nextInt();
- char[][] map = new char[n][];
- for (int i = 0; i < n; ++i) {
- map[i] = nextToken().toCharArray();
- }
- List<Integer> X = new ArrayList<Integer>();
- List<Integer> Y = new ArrayList<Integer>();
- StringBuffer result = new StringBuffer();
- int[][] north = new int[n][m];
- int[][] south = new int[n][m];
- int[][] east = new int[n][m];
- int[][] west = new int[n][m];
- int q = nextInt();
- char []dir = new char[q];
- int []len = new int[q];
- for (int i = 0; i < q; ++i) {
- dir[i] = nextToken().charAt(0);
- len[i] = nextInt();
- }
- for (int i = 0; i < n; ++i) {
- if (map[i][m - 1] != '.' && map[i][m - 1] != '#') {
- X.add(i);
- Y.add(m - 1);
- }
- for (int j = m - 2; j >= 0; --j) {
- if (map[i][j + 1] != '#' && map[i][j] != '#') {
- east[i][j] = east[i][j + 1] + 1;
- }
- if (map[i][j] != '.' && map[i][j] != '#') {
- X.add(i);
- Y.add(j);
- }
- }
- for (int j = 1; j < m; ++j) {
- if (map[i][j - 1] != '#' && map[i][j] != '#') {
- west[i][j] = west[i][j - 1] + 1;
- }
- }
- }
- for (int i = 0; i < m; ++i) {
- for (int j = n - 2; j >= 0; --j) {
- if (map[j + 1][i] != '#' && map[j][i] != '#') {
- south[j][i] = south[j + 1][i] + 1;
- }
- }
- for (int j = 1; j < n; ++j) {
- if (map[j - 1][i] != '#' && map[j][i] != '#') {
- north[j][i] = north[j - 1][i] + 1;
- }
- }
- }
- for (int i = 0; i < X.size(); ++i) {
- int x = X.get(i), y = Y.get(i);
- boolean can = true;
- for (int instr = 0; instr < q && can; ++instr) {
- switch (dir[instr]) {
- case 'E':
- if (east[x][y] >= len[instr]) {
- y += len[instr];
- } else {
- can = false;
- }
- break;
- case 'W':
- if (west[x][y] >= len[instr]) {
- y -= len[instr];
- } else {
- can = false;
- }
- break;
- case 'N':
- if (north[x][y] >= len[instr]) {
- x -= len[instr];
- } else {
- can = false;
- }
- break;
- case 'S':
- if (south[x][y] >= len[instr]) {
- x += len[instr];
- } else {
- can = false;
- }
- break;
- }
- }
- if (can) {
- result.append(map[X.get(i)][Y.get(i)]);
- }
- }
- char []answer = result.toString().toCharArray();
- Arrays.sort(answer);
- if (answer.length == 0) {
- output.println("no solution");
- } else {
- for (char current : answer) {
- output.print(current);
- }
- output.println();
- }
- }
- public void run() {
- try {
- solve();
- } catch (Throwable e) {
- System.err.println(e.getMessage());
- e.printStackTrace();
- System.exit(666);
- } finally {
- output.flush();
- output.close();
- }
- }
- public static void main(String[] args) {
- new TaskD().start();
- }
- private int nextInt() throws IOException {
- return Integer.parseInt(nextToken());
- }
- private long nextLong() throws IOException {
- return Long.parseLong(nextToken());
- }
- private double nextDouble() throws IOException {
- return Double.parseDouble(nextToken());
- }
- private String nextToken() throws IOException {
- while (tokens == null || !tokens.hasMoreTokens()) {
- tokens = new StringTokenizer(input.readLine());
- }
- return tokens.nextToken();
- }
- private BufferedReader input;
- private PrintWriter output;
- private StringTokenizer tokens = null;
- }
Advertisement
Add Comment
Please, Sign In to add comment