第4回 オフラインリアルタイムどう書くの参考問題: Java解答

Fukashigi.java

import static org.junit.Assert.assertEquals;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

import org.junit.Test;

public class Fukashigi {

	protected final String nodeStr = "abcdefghijklmnopqrstuvwxy";

	// 行き先リスト
	protected List<List<Integer>> destDic;

	// すべての道順
	protected List<String> allRoute;

	// 探索中の道順を保持
	protected String tmpString = "";

	public Fukashigi() {
		destDic = new ArrayList<List<Integer>>();
		initAllNode();
	}

	protected void initAllNode() {
		for (int i = 0; i < 24; i++) {
			List<Integer> tmp = new ArrayList<>();
			if ((5 < i && i < 9) || (10 < i && i < 14) || (15 < i && i < 19)) {
				tmp = createRoute4(i);
			} else if ((i == 9) || (i == 14) || (i == 19)) {
				tmp = createRoute3E(i);
			} else if (20 < i && i < 24) {
				tmp = createRoute3S(i);
			} else if (i == 2 || i == 3) {
				tmp = createRoute3N(i);
			} else if (i == 10 || i == 15) {
				tmp = createRoute3W(i);
			} else if (i == 0 || i == 1 || i == 5) {
				tmp = createRoute2TL(i);
			} else if (i == 4) {
				tmp = createRoute2TR(i);
			} else if (i == 20) {
				tmp = createRoute2BL(i);
			}
			destDic.add(tmp);
		}
	}

	protected List<Integer> createRoute4(int i) {
		List<Integer> result = new ArrayList<>();
		result.add(i - 5);
		result.add(i - 1);
		result.add(i + 1);
		result.add(i + 5);
		return result;
	}

	protected List<Integer> createRoute3N(int i) {
		List<Integer> result = new ArrayList<>();
		result.add(i - 1);
		result.add(i + 1);
		result.add(i + 5);
		return result;
	}

	protected List<Integer> createRoute3E(int i) {
		List<Integer> result = new ArrayList<>();
		result.add(i - 5);
		result.add(i - 1);
		result.add(i + 5);
		return result;
	}

	protected List<Integer> createRoute3S(int i) {
		List<Integer> result = new ArrayList<>();
		result.add(i - 5);
		result.add(i - 1);
		result.add(i + 1);
		return result;
	}

	protected List<Integer> createRoute3W(int i) {
		List<Integer> result = new ArrayList<>();
		result.add(i - 5);
		result.add(i + 1);
		result.add(i + 5);
		return result;
	}

	protected List<Integer> createRoute2TL(int i) {
		List<Integer> result = new ArrayList<>();
		result.add(i + 1);
		result.add(i + 5);
		return result;
	}

	protected List<Integer> createRoute2TR(int i) {
		List<Integer> result = new ArrayList<>();
		result.add(i - 1);
		result.add(i + 5);
		return result;
	}

	protected List<Integer> createRoute2BL(int i) {
		List<Integer> result = new ArrayList<>();
		result.add(i - 5);
		result.add(i + 1);
		return result;
	}

	protected int execute(String input) {
		allRoute = new ArrayList<>();
		createAllRoute();
		List<String> result = new ArrayList<>();

		List<String> endList = new ArrayList<>();
		if (input.equals("") == false) {
			String[] deadends = input.split(" ");
			if (deadends != null && 0 < deadends.length) {
				for (String end0 : deadends) {
					String end1 = String.valueOf(end0.charAt(1))
							+ String.valueOf(end0.charAt(0));
					endList.add(end0);
					endList.add(end1);
				}
			}
		}

		Iterator<String> routeite = allRoute.iterator();
		for (; routeite.hasNext();) {
			String oneRoute = routeite.next();
			boolean flag = false;
			Iterator<String> endite = endList.iterator();
			for (; endite.hasNext();) {
				if (oneRoute.contains(endite.next())) {
					flag = true;
				}
			}
			if (flag == false) {
				result.add(oneRoute);
			}
		}
		return result.size();
	}

	/**
	 * すべての道順をallRouteに保存する
	 */
	protected void createAllRoute() {
		tmpString = "a";
		int startNode = 0;
		route(startNode);
	}

	protected void route(int nodeIndex) {
		// nodeIndexの次のノードのリストを得る
		List<Integer> destList = destDic.get(nodeIndex);

		// 次のノードそれぞれに対して、
		Iterator<Integer> iterator = destList.iterator();
		for (; iterator.hasNext();) {
			Integer nextNode = iterator.next();
			// 同じ頂点を二度通ってはいけない
			char destChar = nodeStr.charAt(nextNode);
			if (-1 != tmpString.indexOf(String.valueOf(destChar))) {
				if (iterator.hasNext()) {
					continue;
				} else {
					return;
				}
			}

			tmpString += destChar;
			// 今加えたノードが終点であれば、1つのルートの完成
			if (destChar == 'y') {
				allRoute.add(tmpString);
				tmpString = tmpString.substring(0, tmpString.length() - 1);
				return;
			} else {
				// 続きを探索
				route(nextNode);
				tmpString = tmpString.substring(0, tmpString.length() - 1);
			}
		}
	}

	@Test
	public void testExecute() throws Exception {
		Fukashigi fuga = new Fukashigi();
		assertEquals(8512, fuga.execute(""));
		assertEquals(4256, fuga.execute("af"));
		assertEquals(4256, fuga.execute("xy"));
		assertEquals(184, fuga.execute("pq qr rs st di in ns sx"));
		assertEquals(92, fuga.execute("af pq qr rs st di in ns sx"));
		assertEquals(185, fuga.execute("bg ch di ij no st"));
		assertEquals(16, fuga.execute("bc af ch di no kp mr ns ot pu rs"));
		assertEquals(0, fuga.execute("ab af"));
		assertEquals(0, fuga.execute("ty xy"));
		assertEquals(11, fuga.execute("bg ch ej gh lm lq mr ot rs sx"));
		assertEquals(18, fuga.execute("ty ch hi mn kp mr rs sx"));
		assertEquals(32, fuga.execute("xy ch hi mn kp mr rs sx"));
		assertEquals(50, fuga.execute("ch hi mn kp mr rs sx"));
		assertEquals(621, fuga.execute("ab cd uv wx"));
		assertEquals(685, fuga.execute("gh mn st lq qr"));
		assertEquals(171, fuga.execute("fg gl lm mr rs"));
	}
}