مساله:
مطابق قوانین Boggle ، یک تابع بنویسید که تعیین کند آیا یک رشته، حدس معتبری در یک تخته Boggle است. تخته Boggle یک آرایه دو بعدی از شخصیت های جداگانه است ، به عنوان مثال:
[ ['I','L','A','W'], ['B','N','G','E'], ['I','U','A','O'], ['A','S','R','L'] ]
حدس های معتبر، رشته هایی هستند که می توانند با اتصال سلول های مجاور (افقی ، عمودی یا مورب) بدون استفاده مجدد از سلول های قبلاً استفاده شده ، ایجاد شوند.
به عنوان مثال ، در تابلو فوق “BINGO” ، “LINGO” و “ILNBIA” همه حدس های معتبری خواهند بود ، در حالی که “BUNGIE” ، “BINS” و “SINUS” اینطور نیستند.
تابع شما باید دو آرگومان (یک آرایه دو بعدی و یک رشته) را از ورودی بگیرد و بسته به اینکه آیا رشته طبق قوانین Boggle در آرایه یافت می شود ، درست یا غلط را برگرداند.
موارد تست، اندازه های مختلف آرایه و رشته (آرایه های مربع شکل تا 150×150 و رشته ها تا 150 حروف بزرگ) را ارائه می دهد. شما مجبور نیستید بررسی کنید که آیا این یک کلمه واقعی است یا نه ، فقط باید حدس معتبری باشد.
Description:
Write a function that determines whether a string is a valid guess in a Boggle board, as per the rules of Boggle. A Boggle board is a 2D array of individual characters, e.g.:
[ ['I','L','A','W'], ['B','N','G','E'], ['I','U','A','O'], ['A','S','R','L'] ]
Valid guesses are strings which can be formed by connecting adjacent cells (horizontally, vertically, or diagonally) without re-using any previously used cells.
For example, in the above board “BINGO”, “LINGO”, and “ILNBIA” would all be valid guesses, while “BUNGIE”, “BINS”, and “SINUS” would not.
Your function should take two arguments (a 2D array and a string) and return true or false depending on whether the string is found in the array as per Boggle rules.
Test cases will provide various array and string sizes (squared arrays up to 150×150 and strings up to 150 uppercase letters). You do not have to check whether the string is a real word or not, only if it’s a valid guess.
راه حل ها:
public class Boggle {
private char[][] board;
private int rows;
private int cols;
private String word;
public Boggle(final char[][] board, final String word) {
this.word=word;
this.board=board;
rows=board.length;
if (rows>0) cols=board[0].length;
else cols=0;
}
private boolean recursiveSearch(int r, int c, int charIndex, boolean[][] visited) {
if (charIndex>=word.length()) return true;
char chr=word.charAt(charIndex);
visited[r]=true;
for (int dr=(r==0 ? 0:-1); dr<=(r==rows-1 ? 0:1); dr++)
for (int dc=(c==0 ? 0:-1); dc<=(c==cols-1 ? 0:1); dc++)
if (!visited[r+dr]
&& board[r+dr]==chr
&& recursiveSearch(r+dr,c+dc,charIndex+1,visited))
return true;
visited[r]=false;
return false;
}
public boolean check() {
char c=word.charAt(0);
boolean[][] visited=new boolean[rows][cols];
for (int i=0;i<rows;i++)
for (int j=0;j<cols;j++)
if (board[i][j]==c && recursiveSearch(i,j,1,visited))
return true;
return false;
}
}import java.awt.Point;
import java.util.*;
public class Boggle {
final static private Point[] MOVES = {new Point(-1,-1), new Point(-1,0), new Point(-1,1),
new Point( 0,-1), new Point( 0,1),
new Point( 1,-1), new Point( 1,0), new Point( 1,1)};
private char[][] board;
private String word;
public Boggle(final char[][] board, final String word) {
this.board = board;
this.word = word;
}
public boolean check() { // Do a DFS for each char corresponding to the first letter of the word
for (int x=0 ; x < board.length ; x++)
for (int y=0 ; y < board[x].length ; y++)
if (word.charAt(0) == board[x][y]) {
boolean isPresent = dfsCheck(1, new Point(x,y));
if (isPresent) return true;
}
return false;
}
private boolean dfsCheck(final int iC, final Point p) {
if (iC == word.length()) return true; // Found a full match
char wasC = board[p.x][p.y]; // Archive current cahr under the "pointer"
board[p.x][p.y] = '\0'; // consume
boolean isPresent = Arrays.stream(MOVES)
.map( m -> new Point(m.x+p.x, m.y+p.y) )
.filter( m -> 0 <= m.x && m.x < board.length
&& 0 <= m.y && m.y < board.length
&& board[m.x][m.y] == word.charAt(iC) )
.anyMatch( m -> dfsCheck(iC+1, m) ); // Search for next char at all positions around the current one
board[p.x][p.y] = wasC; // "unconsume" the current char
return isPresent;
}
}import java.util.*;
public class Boggle {
private char[][] board;
private String word;
public Boggle(final char[][] board, final String word) {
this.board = board;
this.word = word;
}
public boolean check() {
int size = board.length;
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (board[i][j] == word.toCharArray()[0]) {
if (word.length() == 1)
return board[i][j] == word.toCharArray()[0];
if (checkNext(word.substring(1), j, i, new boolean[size][size]))
return true;
}
}
}
return false;
}
public boolean checkNext(String text, int x, int y, boolean[][] checked) {
char charNext = text.toCharArray()[0];
checked[y][x] = true;
// up
if (y - 1 >= 0 && isChar(charNext, x, y - 1) && !checked[y - 1][x]) {
if (text.length() == 1 || checkNext(text.substring(1), x, y - 1, checked))
return true;
}
// down
if (y + 1 < board.length && isChar(charNext, x, y + 1) && !checked[y + 1][x]) {
if (text.length() == 1 ||checkNext(text.substring(1), x, y + 1, checked))
return true;
}
// left
if (x - 1 >= 0 && isChar(charNext, x - 1, y) && !checked[y][x - 1]) {
if (text.length() == 1 || checkNext(text.substring(1), x - 1, y, checked))
return true;
}
// right
if (x + 1 < board.length && isChar(charNext, x + 1, y) && !checked[y][x + 1]) {
if (text.length() == 1 || checkNext(text.substring(1), x + 1, y, checked))
return true;
}
// upLeft
if (x - 1 >= 0 && y - 1 >= 0 && isChar(charNext, x - 1, y - 1) && !checked[y - 1][x - 1]) {
if (text.length() == 1 || checkNext(text.substring(1), x - 1, y - 1, checked))
return true;
}
// upRight
if (x + 1 < board.length && y - 1 >= 0 && isChar(charNext, x + 1, y - 1) && !checked[y - 1][x + 1]) {
if (text.length() == 1 || checkNext(text.substring(1), x + 1, y - 1, checked))
return true;
}
// downLeft
if (x - 1 >= 0 && y + 1 < board.length && isChar(charNext, x - 1, y + 1) && !checked[y + 1][x - 1]) {
if (text.length() == 1 || checkNext(text.substring(1), x - 1, y + 1, checked))
return true;
}
// downRight
if (x + 1 < board.length && y + 1 < board.length && isChar(charNext, x + 1, y + 1) && !checked[y + 1][x + 1]) {
if (text.length() == 1 ||checkNext(text.substring(1), x + 1, y + 1, checked))
return true;
}
checked[y][x] = false;
return false;
}
public boolean isChar(char c, int x, int y) {
return board[y][x] == c;
}
}public class Boggle {
private final boolean result;
private static boolean check(String guess, char[][] board, int i, int j, int k){
if (k>=guess.length()) return true;
if ((i<0)||(j<0)||(i>=board.length)||(j>=board[0].length))return false;
if (board[i][j]==guess.charAt(k)){
board[i][j] = 0;
k++;
boolean r = check(guess, board, i-1, j-1,k)|
check(guess, board, i-1, j,k)||
check(guess, board, i-1, j+1,k)||
check(guess, board, i, j-1,k)||
check(guess, board, i, j+1,k)||
check(guess, board, i+1, j-1,k)||
check(guess, board, i+1, j,k)||
check(guess, board, i+1, j+1,k);
board[i][j] = guess.charAt(--k);
return r;
}else
return false;
}
static boolean validGuess(String guess, char[][] board){
for (int i=0; i<board.length;i++)
for (int j=0; j<board[0].length;j++)
if (check(guess, board, i, j, 0)) return true;
return false;
}
public Boggle(final char[][] board, final String word) {
result = validGuess(word, board);
}
public boolean check() {
// Your code here too!
return result;
}
}import java.util.LinkedHashSet;
import java.util.Set;
public class Boggle {
private final char[][] board;
private final String word;
public Boggle(final char[][] board, final String word)
{
this.board = board.clone();
for (int i = 0; i < board.length; i++)
this.board[i] = this.board[i].clone();
this.word = word;
}
public boolean check()
{
final Set<Long> solution = new LinkedHashSet<Long>(this.word.length());
for (int x = 0; x < this.board.length; x++)
for (int y = 0; y < this.board[x].length; y++)
if (this.check(x, y, 0, solution))
return true;
return false;
}
private boolean check(int x, int y, int i, Set<Long> s)
{
if (x < 0 || this.board.length <= x || y < 0 || this.board[x].length <= y)
return false;
if (this.word.length() == i)
return true;
if (this.word.charAt(i++) == this.board[x][y] && s.add((((long) x) << 32) + y))
{
if (this.check(x-1, y+1, i, s) || this.check(x , y+1, i, s) || this.check(x+1, y+1, i, s)
|| this.check(x-1, y , i, s) || this.check(x+1, y , i, s)
|| this.check(x-1, y-1, i, s) || this.check(x , y-1, i, s) || this.check(x+1, y-1, i, s))
return true;
s.remove((((long) x) << 32) + y);
}
return false;
}
}public class Boggle {
private char[][] _board;
private String _word;
private int[][] _flag;
public Boggle(final char[][] board, final String word) {
_board = new char[board.length+2][board[0].length+2];
for(int i = 0; i < _board.length; i++) {
_board[i][0] = ' ';
_board[i][_board[0].length-1] = ' ';
}
for(int i = 0; i < _board[0].length; i++) {
_board[0][i] = ' ';
_board[_board.length - 1][i] = ' ';
}
for(int i = 0; i < board.length;i++) {
for(int j = 0; j < board[0].length;j++) {
_board[i+1][j+1]=board[i][j];
}
}
_word = word;
_flag = new int[board.length+2][board[0].length+2];
for(int i = 0; i < board.length;i++) {
for(int j = 0; j < board[0].length;j++) {
_flag[i][j] = 0;
}
}
}
public boolean check() {
char firstChar = _word.charAt(0);
for(int i = 1; i < _board.length - 1; i++) {
for(int j = 1; j < _board[0].length - 1; j++) {
if(_board[i][j] == firstChar) {
_flag[i][j] = 1;
if(checkNextChar(1, i, j)) {
return true;
}else {
_flag[i][j] = 0;
}
}
}
}
return false;
}
boolean checkNextChar(int charIndex, int x, int y) {
if(charIndex >= _word.length()) {
return true;
}
char c = _word.charAt(charIndex);
int[][] adjacentCells = new int[][] {{x-1, y-1}, {x-1,y}, {x-1, y+1},
{x, y-1}, {x, y+1},
{x+1, y-1}, {x+1, y}, {x+1, y+1}};
for(int l = 0; l < adjacentCells.length; l++) {
int acX = adjacentCells[l][0];
int acY = adjacentCells[l][1];
if(_board[acX][acY] != ' ' && _flag[acX][acY] == 0 && _board[acX][acY] == c) {
_flag[acX][acY] = 1;
if(checkNextChar(charIndex + 1, acX, acY)) {
return true;
} else {
_flag[acX][acY] = 0;
}
}
}
return false;
}
}import java.util.Arrays;
public class Boggle {
char[][] board;
String word;
String[] letters;
public Boggle(final char[][] board, final String word) {
this.board = board;
this.word = word;
letters = word.split("");
}
public boolean check() {
boolean[][] checkedBoard = new boolean[board.length][board[0].length];
for (int x = 0; x < board[0].length; x++) {
for(int y = 0; y < board.length; y++) {
boolean isBoggle = checkBoggle(x,y,0,checkedBoard);
if(isBoggle)
return true;
}
}
return false;
}
public boolean checkBoggle(int x, int y, int i, boolean[][] checkedBoard) {
boolean result = false;
if (x < 0 || y < 0 || x >= board[0].length || y >= board.length)
return false;
if (checkedBoard[y][x] == false) {
checkedBoard[y][x] = true;
if (board[y][x] == letters[i].charAt(0)) {
i++;
if(i >= word.length())
return true;
result = result || checkBoggle(x-1, y, i, checkedBoard);
result = result || checkBoggle(x-1, y+1, i, checkedBoard);
result = result || checkBoggle(x-1, y-1, i, checkedBoard);
result = result || checkBoggle(x+1, y, i, checkedBoard);
result = result || checkBoggle(x+1, y+1, i, checkedBoard);
result = result || checkBoggle(x+1, y-1, i, checkedBoard);
result = result || checkBoggle(x, y+1, i, checkedBoard);
result = result || checkBoggle(x, y-1, i, checkedBoard);
}
checkedBoard[y][x] = false;
}
return result;
}
}public class Boggle {
char[][] board;
String word;
int[][] dir = {{0,1},{0,-1},{1,0},{-1,0},{1,1},{-1,1},{-1,-1},{1,-1}};
int m, n;
public Boggle(final char[][] board, final String word) {
this.board = board;
this.word = word;
m = board.length;
n = m == 0 ? 0 : board[0].length;
}
public boolean check() {
for (int x = 0; x < m; ++x)
for (int y = 0; y < n; ++y)
if (dfs(0, x, y))
return true;
return false;
}
private boolean dfs(int idx, int x, int y) {
if (idx == word.length()) return true;
if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] == '*') return false;
if (board[x][y] == word.charAt(idx)) {
board[x][y] = '*';
for (int i = 0; i < dir.length; ++i) {
if (dfs(idx+1, x+dir[i][0], y+dir[i][1])) {
board[x][y] = word.charAt(idx);
return true;
}
}
board[x][y] = word.charAt(idx);
}
return false;
}
}
