55 lines
1.4 KiB
C#
55 lines
1.4 KiB
C#
public class Solution {
|
|
private struct Solver {
|
|
char[][] Board { get; init; }
|
|
int Height { get => Board.Length; }
|
|
int Width { get => Board[0].Length; }
|
|
|
|
string Word { get; init; }
|
|
|
|
public Solver(char[][] board, string word) {
|
|
Board = board;
|
|
Word = word;
|
|
}
|
|
|
|
private bool Has(int y, int x)
|
|
=> y >= 0 && y < Height && x >= 0 && x < Width;
|
|
|
|
private bool DFS(int y, int x, int i) {
|
|
if (i == Word.Length) {
|
|
return true;
|
|
}
|
|
|
|
if (!Has(y, x) || Board[y][x] == '!' || Word[i] != Board[y][x]) {
|
|
return false;
|
|
}
|
|
|
|
var tmp = Board[y][x];
|
|
Board[y][x] = '!';
|
|
|
|
foreach (int d in new int[] { 1, -1 }) {
|
|
if (DFS(y + d, x, i + 1) || DFS(y, x + d, i + 1)) {
|
|
return true;
|
|
}
|
|
}
|
|
|
|
Board[y][x] = tmp;
|
|
return false;
|
|
}
|
|
|
|
public bool Solve() {
|
|
for (int y = 0; y < Height; ++y) {
|
|
for (int x = 0; x < Width; ++x) {
|
|
if (DFS(y, x, 0)) {
|
|
return true;
|
|
}
|
|
}
|
|
}
|
|
|
|
return false;
|
|
}
|
|
}
|
|
|
|
public bool Exist(char[][] board, string word) {
|
|
return new Solver(board, word).Solve();
|
|
}
|
|
}
|