#212336 (Java21) No.585 工夫のないパズル

提出ソース

結果

問題	No.585 工夫のないパズル
ユーザー	uwi
提出日時	2017-10-27 23:53:15
言語	Java21 (openjdk 21)
結果	AC
実行時間	100 ms / 2,000 ms
コード長	6,846 bytes
コンパイル時間	6,731 ms
コンパイル使用メモリ	90,332 KB
実行使用メモリ	53,880 KB
最終ジャッジ日時	2023-08-14 07:52:08
合計ジャッジ時間	6,489 ms
ジャッジサーバーID （参考情報）	judge15 / judge13

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	96 ms 52,652 KB
testcase_01	AC	89 ms 52,424 KB
testcase_02	AC	97 ms 53,880 KB
testcase_03	AC	93 ms 52,548 KB
testcase_04	AC	96 ms 53,660 KB
testcase_05	AC	92 ms 52,732 KB
testcase_06	AC	91 ms 52,424 KB
testcase_07	AC	91 ms 52,444 KB
testcase_08	AC	92 ms 52,716 KB
testcase_09	AC	91 ms 52,420 KB
testcase_10	AC	90 ms 52,644 KB
testcase_11	AC	89 ms 52,744 KB
testcase_12	AC	100 ms 53,688 KB
testcase_13	AC	100 ms 53,392 KB
testcase_14	AC	100 ms 53,164 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

package contest171027;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.List;
import java.util.Queue;

public class E {
	InputStream is;
	PrintWriter out;
	String INPUT = "";
	List<String> ops = new ArrayList<>();
	char[][] map;
	
	void print()
	{
		for(char[] row : map){
			tr(new String(row));
		}
	}
	
	void solve()
	{
		map = nm(4, 4);
		
		for(int i = 0;i < 3;i++){
			inner:
			for(int j = 0;j < 3;j++){
				if(map[i][j] != 'A' + i*4 + j){
					for(int k = 0;k < 4;k++){
						for(int l = 0;l < 4;l++){
							if(map[k][l] == 'A' + i*4 + j){
								if(i == k){
									rotateLeft(i, j, k, l, k+1, l);
								}else{
									if(l < 3){
										r(k, 3-l);
//										print();
									}
									rotateRight(i, j, i, 3, k, 3);
								}
								continue inner;
							}
						}
					}
					throw new RuntimeException();
				}
			}
		}
//		print();
		// ...0
		// ...1
		// ...2
		// 3456
		
		String rem = "DHLMNOP";
		int[] a = new int[7];
		a[0] = rem.indexOf(map[0][3]);
		a[1] = rem.indexOf(map[1][3]);
		a[2] = rem.indexOf(map[2][3]);
		a[3] = rem.indexOf(map[3][0]);
		a[4] = rem.indexOf(map[3][1]);
		a[5] = rem.indexOf(map[3][2]);
		a[6] = rem.indexOf(map[3][3]);
		
//		tr(ops.size());
		int icode = encPerm(a);
		Queue<Integer> q = new ArrayDeque<>();
		char[] prev = new char[5040];
		int[] from = new int[5040];
		q.add(icode);
		prev[icode] = 'X';
		while(!q.isEmpty()){
			int cur = q.poll();
			int[] b = decPerm(cur, 7);
			// C++
			{
				{int d = b[6]; b[6] = b[2] ; b[2] = b[1]; b[1] = b[0]; b[0] = d;}
				int code = encPerm(b);
				if(prev[code] == 0){
					prev[code] = 'C';
					from[code] = cur;
					q.add(code);
				}
				{int d = b[0]; b[0] = b[1] ; b[1] = b[2]; b[2] = b[6]; b[6] = d;}
			}
			{
				{int d = b[6]; b[6] = b[5] ; b[5] = b[4]; b[4] = b[3]; b[3] = d;}
				int code = encPerm(b);
				if(prev[code] == 0){
					prev[code] = 'R';
					from[code] = cur;
					q.add(code);
				}
				{int d = b[3]; b[3] = b[4] ; b[4] = b[5]; b[5] = b[6]; b[6] = d;}
			}
		}
		int last = 0;
		StringBuilder lo = new StringBuilder();
		while(last != icode){
			lo.append(prev[last]);
			last = from[last];
		}
		lo = lo.reverse();
		for(char c : lo.toString().toCharArray()){
			if(c == 'C'){
				c(3, 1);
			}else{
				r(3, 1);
			}
		}
		
//		List<String> to = new ArrayList<>();
//		String prefix = "";
//		for(String line : ops){
//			String lp = line.substring(0, 3);
//			if(prefix.
//		}
		
		assert ops.size() <= 100;
		out.println(ops.size());
		for(String line : ops){
			out.println(line);
		}
	}
	
	public static int encPerm(int[] a)
	{
		int n = a.length;
		int used = 0;
		int ret = 0;
		for(int i = 0;i < n;i++){
			ret = ret * (n - i) + a[i] - Integer.bitCount(used & ((1<<a[i]) - 1));
			used |= 1<<a[i];
		}
		return ret;
	}
	
	public static int[] decPerm(int c, int n)
	{
		int[] a = new int[n];
		for(int i = n - 1;i >= 0;c /= n - i, i--){
			int v = c % (n - i);
			a[i] = v;
			for(int j = i + 1;j <= n - 1;j++){
				if(v <= a[j])a[j]++;
			}
		}
		return a;
	}

	
	void r(int r, int x)
	{
		if(!(r >= 0 && r <= 3))throw new RuntimeException();
		if(!(x >= 1 && x <= 3))throw new RuntimeException();
		ops.add("R " + r + " " + x);
		char[] temp = Arrays.copyOf(map[r], 4);
		for(int i = 0;i < 4;i++){
			map[r][(i+x)%4] = temp[i];
		}
	}
	
	void c(int c, int x)
	{
		if(!(c >= 0 && c <= 3))throw new RuntimeException();
		if(!(x >= 1 && x <= 3))throw new RuntimeException();
		ops.add("C " + c + " " + x);
		char[] temp = new char[4];
		for(int i = 0;i < 4;i++)temp[i] = map[i][c];
		for(int i = 0;i < 4;i++){
			map[(i+x)%4][c] = temp[i];
		}
	}
	
	void rotateLeft(int i, int j, int k, int l, int m, int n)
	{
		c(l, k-m+4&3);
		r(i, l-j+4&3);
		c(l, m-k+4&3);
		r(i, j-l+4&3);
	}
	
	void rotateRight(int i, int j, int k, int l, int m, int n)
	{
		r(i, l-j+4&3);
		c(l, k-m+4&3);
		r(i, j-l+4&3);
		c(l, m-k+4&3);
	}
	
	void swap(int r1, int c1, int r2, int c2)
	{
		
	}
	
	void run() throws Exception
	{
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		
		long s = System.currentTimeMillis();
		solve();
		out.flush();
		if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
//		Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){
//			@Override
//			public void run() {
//				long s = System.currentTimeMillis();
//				solve();
//				out.flush();
//				if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
//			}
//		};
//		t.start();
//		t.join();
	}
	
	public static void main(String[] args) throws Exception { new E().run(); }
	
	private byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;
	
	private int readByte()
	{
		if(lenbuf == -1)throw new InputMismatchException();
		if(ptrbuf >= lenbuf){
			ptrbuf = 0;
			try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
			if(lenbuf <= 0)return -1;
		}
		return inbuf[ptrbuf++];
	}
	
	private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
	private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
	
	private double nd() { return Double.parseDouble(ns()); }
	private char nc() { return (char)skip(); }
	
	private String ns()
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	
	private char[] ns(int n)
	{
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while(p < n && !(isSpaceChar(b))){
			buf[p++] = (char)b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}
	
	private int[] na(int n)
	{
		int[] a = new int[n];
		for(int i = 0;i < n;i++)a[i] = ni();
		return a;
	}
	
	private long[] nal(int n)
	{
		long[] a = new long[n];
		for(int i = 0;i < n;i++)a[i] = nl();
		return a;
	}
	
	private char[][] nm(int n, int m) {
		char[][] map = new char[n][];
		for(int i = 0;i < n;i++)map[i] = ns(m);
		return map;
	}
	
	private int[][] nmi(int n, int m) {
		int[][] map = new int[n][];
		for(int i = 0;i < n;i++)map[i] = na(m);
		return map;
	}
	
	private int ni() { return (int)nl(); }
	
	private long nl()
	{
		long num = 0;
		int b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}

yukicoder

結果

テストケース

ソースコード