Submission #4087944


Source Code Expand

Copy
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.stream.Stream;

public class Main {

	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		MyInput in = new MyInput(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskX solver = new TaskX();
		solver.solve(1, in, out);
		out.close();
	}

	static int INF = 1 << 30;
	static long LINF = 1L << 55;
	static int MOD = 1000000007;
//	static int[] mh4 = { 0, -1, 1, 0 };
//	static int[] mw4 = { -1, 0, 0, 1 };
	static int[] mh4 = { -1, 1, 0,  0 };
	static int[] mw4 = {  0, 0, 1, -1 };

	static int[] mh8 = { -1, -1, -1, 0, 0, 1, 1, 1 };
	static int[] mw8 = { -1, 0, 1, -1, 1, -1, 0, 1 };

	static class TaskX {

		int n, m, k;
		@SuppressWarnings("unchecked")
		public void solve(int testNumber, MyInput in, PrintWriter out) {

			n = in.nextInt(); m = in.nextInt(); k = in.nextInt();
			char[] d = in.nextChars();
			char[][] s = new char[n][m];
			int sh = -1, sw = -1, gh = -1, gw = -1;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					s[i][j] = in.nextChar();
					if (s[i][j] == 'S') {
						sh = i;
						sw = j;
					}
					if (s[i][j] == 'G') {
						gh = i;
						gw = j;
					}
				}
			}
			List<Integer>[] g = new ArrayList[4];
			g = Stream.generate(ArrayList::new).limit(4).toArray(List[]::new);
			for (int i = 0; i < 2*k; i++) {
				if (d[i%k] == 'U') g[0].add(i);
				if (d[i%k] == 'D') g[1].add(i);
				if (d[i%k] == 'R') g[2].add(i);
				if (d[i%k] == 'L') g[3].add(i);
			}

			long[][] w = new long[k][4];
			for (int t = 0; t < k; t++) {
				for (int i = 0; i < 4; i++) {
					int idx = lowerBound(g[i], t);
					if (g[i].isEmpty()) {
						w[t][i] = LINF;
						continue;
					}
					int v = g[i].get(idx);
					w[t][i] = v - t + 1;
				}
			}

			long[][] cost = new long[n][m];
			PriorityQueue<T> pq = new PriorityQueue<>();
			fill(cost, LINF);
			cost[sh][sw] = 0;
			pq.add(new T(new P(sh, sw), 0));

			while (!pq.isEmpty()) {
				T tup = pq.remove();
				if (tup.c > cost[tup.p.h][tup.p.w]) continue;

				int nh = tup.p.h, nw = tup.p.w;
				int ntime = (int)(cost[tup.p.h][tup.p.w] % k);
				for (int i = 0; i < 4; i++) {
					int mh = nh + mh4[i];
					int mw = nw + mw4[i];
					if (isInside(mh, mw) && s[mh][mw] != '#') {
						if (cost[nh][nw] + w[ntime][i] < cost[mh][mw]) {
							cost[mh][mw] = cost[nh][nw] + w[ntime][i];
							pq.add(new T(new P(mh, mw), cost[mh][mw]));
						}
					}
				}
			}

			out.println(cost[gh][gw] == LINF ? -1 : cost[gh][gw]);
		}

		boolean isInside(int i, int j) {
			return 0 <= i && i < n && 0 <= j && j < m;
		}

		class P {
			int h, w;

			public P(int h, int w) {
				super();
				this.h = h;
				this.w = w;
			}

			@Override
			public String toString() {
				return "P [h=" + h + ", w=" + w + "]";
			}

		}

		class T implements Comparable<T> {
			P p;
			long c;

			@Override
			public int compareTo(T o) {
				return Long.compare(this.c, o.c);
			}

			public T(P p, long c) {
				super();
				this.p = p;
				this.c = c;
			}


			@Override
			public String toString() {
				return "T [p=" + p + ", c=" + c + "]";
			}

		}
	}

	static void fill(long[][] a, long v) {
		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a[0].length; j++) {
				a[i][j] = v;
			}
		}
	}

	static void print(int[][] a, PrintWriter out) {
		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a[0].length; j++) {
				if (j > 0)
					out.print(" ");
				out.print(a[i][j]);
			}
			out.print("\n");
		}
	}

	public static int lowerBound(List<Integer> a, int obj) {
		int l = 0, r = a.size() - 1;
		while (r - l >= 0) {
			int c = (l + r) / 2;
			if (obj <= a.get(c)) {
				r = c - 1;
			} else {
				l = c + 1;
			}
		}
		return l;
	}

	static class MyInput {
		private final BufferedReader in;
		private static int pos;
		private static int readLen;
		private static final char[] buffer = new char[1024 * 8];
		private static char[] str = new char[500 * 8 * 2];
		private static boolean[] isDigit = new boolean[256];
		private static boolean[] isSpace = new boolean[256];
		private static boolean[] isLineSep = new boolean[256];

		static {
			for (int i = 0; i < 10; i++) {
				isDigit['0' + i] = true;
			}
			isDigit['-'] = true;
			isSpace[' '] = isSpace['\r'] = isSpace['\n'] = isSpace['\t'] = true;
			isLineSep['\r'] = isLineSep['\n'] = true;
		}

		public MyInput(InputStream is) {
			in = new BufferedReader(new InputStreamReader(is));
		}

		public int read() {
			if (pos >= readLen) {
				pos = 0;
				try {
					readLen = in.read(buffer);
				} catch (IOException e) {
					throw new RuntimeException();
				}
				if (readLen <= 0) {
					throw new MyInput.EndOfFileRuntimeException();
				}
			}
			return buffer[pos++];
		}

		public int nextInt() {
			int len = 0;
			str[len++] = nextChar();
			len = reads(len, isSpace);
			int i = 0;
			int ret = 0;
			if (str[0] == '-') {
				i = 1;
			}
			for (; i < len; i++)
				ret = ret * 10 + str[i] - '0';
			if (str[0] == '-') {
				ret = -ret;
			}
			return ret;
		}

		public long nextLong() {
			int len = 0;
			str[len++] = nextChar();
			len = reads(len, isSpace);
			int i = 0;
			long ret = 0;
			if (str[0] == '-') {
				i = 1;
			}
			for (; i < len; i++)
				ret = ret * 10 + str[i] - '0';
			if (str[0] == '-') {
				ret = -ret;
			}
			return ret;
		}

		public char nextChar() {
			while (true) {
				final int c = read();
				if (!isSpace[c]) {
					return (char) c;
				}
			}
		}

		public String nextString() {
			return new String(nextChars());
		}

		public char[] nextChars() {
			int len = 0;
			str[len++] = nextChar();
			len = reads(len, isSpace);
			return Arrays.copyOf(str, len);
		}

		public char[][] next2DChars(int h, int w) {
			char[][] s = new char[h][w];
			for (int i = 0; i < h; i++) {
				s[i] = nextChars();
			}
			return s;
		}

		int reads(int len, boolean[] accept) {
			try {
				while (true) {
					final int c = read();
					if (accept[c]) {
						break;
					}
					if (str.length == len) {
						char[] rep = new char[str.length * 3 / 2];
						System.arraycopy(str, 0, rep, 0, str.length);
						str = rep;
					}
					str[len++] = (char) c;
				}
			} catch (MyInput.EndOfFileRuntimeException e) {
			}
			return len;
		}

		public int[] nextIntArray(final int n) {
			final int[] res = new int[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextInt();
			}
			return res;
		}

		public int[] nextIntArray1Index(final int n) {
			final int[] res = new int[n + 1];
			for (int i = 1; i < n + 1; i++) {
				res[i] = nextInt();
			}
			return res;
		}

		public int[] nextIntArrayDec(final int n) {
			final int[] res = new int[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextInt() - 1;
			}
			return res;
		}

		public long[] nextLongArray(final int n) {
			final long[] res = new long[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextLong();
			}
			return res;
		}

		public long[] nextLongArray1Index(final int n) {
			final long[] res = new long[n + 1];
			for (int i = 1; i < n + 1; i++) {
				res[i] = nextLong();
			}
			return res;
		}

		public long[] nextLongArrayDec(final int n) {
			final long[] res = new long[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextLong() - 1;
			}
			return res;
		}

		public double nextDouble() {
			return Double.parseDouble(nextString());
		}

		public double[] nextDoubleArray(int n) {
			double[] res = new double[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextDouble();
			}
			return res;
		}

		static class EndOfFileRuntimeException extends RuntimeException {
		}

	}

}

Submission Info

Submission Time
Task E - 迷路
User tutuz
Language Java8 (OpenJDK 1.8.0)
Score 500
Code Size 8226 Byte
Status
Exec Time 740 ms
Memory 80308 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0
All 500 / 500 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt 166 ms 24276 KB
02.txt 170 ms 24276 KB
03.txt 160 ms 26708 KB
04.txt 154 ms 23372 KB
05.txt 173 ms 25812 KB
06.txt 678 ms 77932 KB
07.txt 726 ms 77088 KB
08.txt 697 ms 73468 KB
09.txt 708 ms 74388 KB
10.txt 679 ms 77272 KB
11.txt 644 ms 79500 KB
12.txt 678 ms 78052 KB
13.txt 675 ms 80308 KB
14.txt 740 ms 75320 KB
15.txt 658 ms 77160 KB
16.txt 608 ms 75736 KB
17.txt 703 ms 73432 KB
18.txt 649 ms 79464 KB
19.txt 653 ms 75408 KB
20.txt 712 ms 77056 KB
21.txt 559 ms 76996 KB
22.txt 613 ms 76528 KB
23.txt 620 ms 74992 KB
24.txt 618 ms 76640 KB
25.txt 586 ms 74440 KB
26.txt 564 ms 75260 KB
27.txt 647 ms 79492 KB
28.txt 605 ms 79072 KB
29.txt 570 ms 77308 KB
30.txt 598 ms 76336 KB
31.txt 326 ms 53260 KB
32.txt 314 ms 51520 KB
33.txt 324 ms 53592 KB
34.txt 321 ms 51036 KB
35.txt 312 ms 49388 KB
36.txt 327 ms 52576 KB
37.txt 320 ms 50744 KB
38.txt 313 ms 51544 KB
39.txt 323 ms 53460 KB
40.txt 402 ms 65276 KB
41.txt 160 ms 26708 KB
s1.txt 151 ms 28116 KB
s2.txt 161 ms 23764 KB
s3.txt 165 ms 24404 KB