[SWEA]2819:メッシュボードに接続されている数字

🔗 質問リンク

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7I5fgqEogDFAXB&categoryId=AV7I5fgqEogDFAXB&categoryType=CODE

🤔 質問する

4×4つの大きさの格子板があります.メッシュボードの各メッシュには、0～9の間のメッシュがあります. 数字が書いてあります.
メッシュボード上の任意の位置から、 東西南北 隣接するグリッドを4方向に6回移動し、各セルの数値を順番に接続します. 合わせて7桁あります.
移動時に一度通過したメッシュを再配置 0で始まる0102001を作成することもできます.
ただし、グリッドの外に移動することはできないとします.
メッシュボードを指定すると、異なる 7桁の数字を求めるプログラムを作成してください.

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

深度優先探索(DFS)を使用してグリッド上のすべての数字を結合し、ハイフンの長さが7のときにSetに入れて重複する文字を除去します.
そしてSetにSizeを出力すると問題が解決します.

🚩Javaコード

package com.algorithm.SWEA.D4;

import java.io.*;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Solution_2829 {
    private static Set<String> set;
    private static final int[] DX = {1, -1, 0, 0};
    private static final int[] DY = {0, 0, 1, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int TC = Integer.parseInt(br.readLine());
        int[][] board = new int[4][4];
        for (int N = 0; N < TC; N++) {
            set = new HashSet<>();
            for (int i = 0; i < 4; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int j = 0; j < 4; j++)
                    board[i][j] = Integer.parseInt(st.nextToken());
            }

            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 4; j++) {
                    dfs(board, i, j);
                }
            }

            bw.write("#" + (N + 1) + " ");
            bw.write(String.valueOf(set.size()));
            bw.newLine();
        }

        br.close();
        bw.close();
    }

    private static void dfs(int[][] board, int i, int j) {
        String s = "";
        dfsUtil(board, i, j, s);
    }

    private static void dfsUtil(int[][] board, int i, int j, String s) {
        if (s.length() == 7) {
            set.add(s);
            return;
        }
        s += board[i][j];
        for (int k = 0; k < DX.length; k++) {
            int nx = i + DX[k];
            int ny = j + DY[k];
            if (nx >= 0 && nx < 4 && ny >= 0 && ny < 4)
                dfsUtil(board, nx, ny, s);
        }
    }
}

💬 コメント

これはDFSを単純に利用した完全探索問題のようである.D 4級にとっては簡単な問題のようです.