Submission #60848

---

Source Code Expand

import java.util.Arrays;

public class Main{

	int h, w, N, INF = 1<<25;
	char[][] m;
	int[][] d = {{-1,0},{0,1},{1,0},{0,-1}};
	char[] s;
	int[][][][] next, dp;
	
	int get(int i, int j, int k, int now){
		if(now==N)return 0;
		if(dp[i][j][k][now]!=-1)return dp[i][j][k][now];
		int res = INF;
		for(int dir=0;dir<4;dir++){
			if(dir==k)continue;
			int c = next[i][j][dir][s[now]-'a'];
			if(c!=INF)res = Math.min(res, c+get(i+c*d[dir][0], j+c*d[dir][1], dir, now+1));
		}
		return dp[i][j][k][now] = res;
	}
	
	void run() {
		Scanner sc = new Scanner();
		h = sc.nextInt(); w = sc.nextInt(); N = sc.nextInt();
		s = sc.next().toCharArray();
		m = new char[h][];
		for(int i=0;i<h;i++)m[i]=sc.next().toCharArray();
		next = new int[h][w][4][26];
		for(int i=0;i<h;i++)for(int j=0;j<w;j++)for(int k=0;k<4;k++)for(int c=0;c<26;c++){
			next[i][j][k][c] = INF;
			int pi = i+d[k][0], pj = j+d[k][1];
			for(;;){
				if(pi<0||h<=pi||pj<0||w<=pj)break;
				if(m[pi][pj]-'a'==c){
					next[i][j][k][c] = Math.abs(i-pi)+Math.abs(j-pj);break;
				}
				pi+=d[k][0]; pj+=d[k][1];
			}
		}
		dp = new int[h][w][4][N];
		for(int i=0;i<h;i++)for(int j=0;j<w;j++)for(int k=0;k<4;k++)for(int l=0;l<N;l++)dp[i][j][k][l]=-1;
		int res = INF;
		for(int i=0;i<h;i++)for(int j=0;j<w;j++)for(int k=0;k<4;k++)res=Math.min(res, get(i, j, k, 0));
		System.out.println(res==INF?-1:res);
	}

	void debug(Object... o) {
		System.out.println(Arrays.deepToString(o));
	}

	class Scanner {
		int nextInt() {
			try {
				int c = System.in.read();
				while (c != '-' && (c < '0' || '9' < c))
					c = System.in.read();
				if (c == '-') return -nextInt();
				int res = 0;
				do {
					res *= 10;
					res += c - '0';
					c = System.in.read();
				} while ('0' <= c && c <= '9');
				return res;
			} catch (Exception e) {
				return -1;
			}
		}
		long nextLong() {
			try {
				int c = System.in.read();
				while (c != '-' && (c < '0' || '9' < c))
					c = System.in.read();
				if (c == '-') return -nextLong();
				long res = 0;
				do {
					res *= 10;
					res += c - '0';
					c = System.in.read();
				} while ('0' <= c && c <= '9');
				return res;
			} catch (Exception e) {
				return -1;
			}
		}
		double nextDouble() {
			return Double.parseDouble(next());
		}
		String next() {
			try {
				StringBuilder res = new StringBuilder("");
				int c = System.in.read();
				while (Character.isWhitespace(c))
					c = System.in.read();
				do {
					res.append((char) c);
				} while (!Character.isWhitespace(c = System.in.read()));
				return res.toString();
			} catch (Exception e) {
				return null;
			}
		}
		String nextLine(){
			try{
				StringBuilder res =new StringBuilder("");
				int c = System.in.read();
				while (c=='\r' || c=='\n')
					c = System.in.read();
				do {
					res.append((char) c);
					c = System.in.read();
				} while (c!='\r' && c!='\n');
				return res.toString();
			}catch (Exception e) {
				return null;
			}
		}
	}
	
	public static void main(String... args) {
		new Main().run();
	}
}

Submission Info

Judge Result