白駿-1987号(アルファベット)
質問元:https://www.acmicpc.net/problem/1987
質問する
縦列R格子、横列C格子の表形板があります.碁盤の各段には大文字が書かれていて、左上隅(1行1列)に馬が置かれています.
マルコは上下左右に隣接する4つの格子のうちの1つに移動し、新しく移動した格子のアルファベットは以前のすべての格子のアルファベットと異なる必要があります.つまり、同じ文字が書かれたセルを2回通過することはできません.
左上から、プログラムを作成して、出馬を求めるのはせいぜいいくつかの格を通過することができます.馬が通った車両には左上隅の車両も含まれている.
DFSによって解決された問題 文字の個数(26文字)に基づいてブール配列を宣言し、使用するか否かを判断する. 候補者を探索し、可能な限り復帰させ、突き当たりまで行ってすべての状況を調べる際に、続けられなければその時の値を保存し、後部車両に再移動することを実現した.
質問する
縦列R格子、横列C格子の表形板があります.碁盤の各段には大文字が書かれていて、左上隅(1行1列)に馬が置かれています.
マルコは上下左右に隣接する4つの格子のうちの1つに移動し、新しく移動した格子のアルファベットは以前のすべての格子のアルファベットと異なる必要があります.つまり、同じ文字が書かれたセルを2回通過することはできません.
左上から、プログラムを作成して、出馬を求めるのはせいぜいいくつかの格を通過することができます.馬が通った車両には左上隅の車両も含まれている.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
private static int result;
private static int temp;
private static int[][] directions = {
{ -1, 0 }, // 상
{ 1, 0 }, // 하
{ 0, -1 }, // 좌
{ 0, 1 }, // 우
};
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
int R = Integer.parseInt(tokenizer.nextToken());
int C = Integer.parseInt(tokenizer.nextToken());
char[][] board = new char[R][C];
for (int i = 0; i < R; i++) {
board[i] = reader.readLine().toCharArray();
}
boolean[] flag = new boolean[26]; // 'A' -> 0
dfs(board, flag, 0, 0, R, C);
System.out.println(result);
}
private static void dfs(char[][] board, boolean[] flag, int row, int col, int R, int C) {
flag[board[row][col] - 'A'] = true; // 사용 처리
temp++;
for (int i = 0; i < 4; i++) {
int dy = row + directions[i][0];
int dx = col + directions[i][1];
if (dy >= 0 && dy < R && dx >= 0 && dx < C) {
if (!flag[board[dy][dx] - 'A']) {
dfs(board, flag, dy, dx, R, C);
}
}
}
flag[board[row][col] - 'A'] = false; // 사용 처리
result = Math.max(result, temp);
temp--;
}
}
Reference
この問題について(白駿-1987号(アルファベット)), 我々は、より多くの情報をここで見つけました https://velog.io/@ghc1124/백준-1987번알파벳テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol