Tools: VSCode | Source Code: GitHub
This Java program is designed to search for a given word within a grid of letters. The word can be found in a straight line horizontally, vertically, or diagonally. Additionally, the word can be split into two segments forming a right angle at one of its letters. The program reads input values, processes the grid, and counts the number of valid occurrences of the word before printing the result.
First, the program reads the word to be searched, followed by the dimensions of the grid (rows and columns). It then constructs a 2D character array to store the grid, ensuring that each letter is accessible for searching. The input is taken in a structured manner to facilitate easy traversal of the grid during the search process.
The main logic of the program involves checking each cell in the grid to determine whether the word can be formed starting from that position. This is done by exploring eight possible directions: left, right, up, down, and the four diagonal directions. For each direction, the program verifies if the entire word can be constructed without exceeding the grid boundaries.
In addition to checking straight-line occurrences, the program also accounts for right-angle formations. This means that after following one direction for part of the word, it switches to a perpendicular direction to complete the word. To achieve this, the program first checks the validity of the first segment before verifying the continuation in another direction.
Throughout the process, a counter keeps track of all valid occurrences of the word in the grid. Once all possible positions have been examined, the program prints the final count, which represents the number of times the word appears following the given rules. This approach ensures that all possible placements are considered efficiently.
public class CCCWordHunt {
static int rows, cols;
static char[][] grid;
static String word;
static int wordLength;
static int[][] directions = {
{0, 1}, {1, 0}, {1, 1}, {-1, 1},
{0, -1}, {-1, 0}, {-1, -1}, {1, -1}
};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
word = sc.next();
wordLength = word.length();
rows = sc.nextInt();
cols = sc.nextInt();
grid = new char[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
grid[i][j] = sc.next().charAt(0);
}
}
int count = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == word.charAt(0)) {
count += findWord(i, j);
}
}
}
System.out.println(count);
}
static int findWord(int x, int y) {
int found = 0;
for (int[] dir : directions) {
int newX = x, newY = y, int index = 0;
while (index < wordLength && isValid(newX, newY) && grid[newX][newY] == word.charAt(index)) {
newX += dir[0];
newY += dir[1];
index++;
}
if (index == wordLength) found++;
for (int[] dir2 : directions) {
if (dir2 == dir) continue;
newX = x + dir[0] * (index - 1);
newY = y + dir[1] * (index - 1);
int newIndex = index;
while (newIndex < wordLength && isValid(newX, newY) && grid[newX][newY] == word.charAt(newIndex)) {
newX += dir2[0];
newY += dir2[1];
newIndex++;
}
}
}
return found;
}
static boolean isValid(int x, int y) {
return x >= 0 && x < rows && y >= 0 && y < cols;
}
}