BOJ - 17370

BOJ - 17370

(質問:https://www.acmicpc.net/problem/17370)

UCPC 2021を準備している間に、2019 UCPCI号の質問に答えました。

トラブルシューティング方法

まず六角形を上と下に押し出すと、その両側に長方形を形成することができる.このときアリが移動する場所は[][]配列で確認できる.

Nの制限が22であるため、2^22を行ってもTLEは発生しないため、DFSが実行される.

dfsの実行中、nextStateは(state+1)%6、(6+state-1)%6に設定されます.

dfs実行終了条件はcount=Nであり、各ステップがnextStateのx、y値に対応するアクセスはtrueであり、countがN-1の場合に答えを増加させる.

コード#コード#

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;

public class Main {
	public static int N;
	public static long answer = 0;
	public static int[] dx = {0, -1, -1, 0, 1, 1};
	public static int[] dy = {1, 0, 0, -1, 0, 0};
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		solve(-1, 25, 25, 0, new boolean[50][50], "");
		
		System.out.println(answer);
	}
	
	public static void solve(int count, int x, int y, int state, boolean[][] visited, String str) {
		if(count == -1) {
			visited[x][y] = true;
			visited[x + dx[0]][y + dy[0]] = true;
			solve(0, x + dx[0], y + dy[0], 0, visited, "");
		}
		else if(count == N) {
			return;
		}
		else {
			// i - 1 % 6
			int nextState = (6 + state - 1) % 6;
			
			if(visited[x + dx[nextState]][y + dy[nextState]]) {
				if(count == N - 1) answer++;
			}
			else {
				visited[x + dx[nextState]][y + dy[nextState]] = true;
				solve(count + 1, x + dx[nextState], y + dy[nextState], nextState, visited, str + nextState);
				visited[x + dx[nextState]][y + dy[nextState]] = false;
			}
			
			// i + 1 % 6
			nextState = (state + 1) % 6;
			
			if(visited[x + dx[nextState]][y + dy[nextState]]) {
				if(count == N - 1) answer++;
			}
			else {
				visited[x + dx[nextState]][y + dy[nextState]] = true;
				solve(count + 1, x + dx[nextState], y + dy[nextState], nextState, visited, str + nextState);
				visited[x + dx[nextState]][y + dy[nextState]] = false;
			}
		}
	}

}

ポスト

途中で答えを増やしたり、返したりするミスがあり、3回提出すれば正解です.
六角形を作り始めたばかりの考えは難しい.それ以来,簡単なdfs問題で解決できる.