package Backtrace;

/**
 * @author dx
 * @version 1.0
 * @date 2022年6月2日 10:30
 * @description: 力扣79
 */
public class Find_Word {
}
class Find_Word_Solution{
 public boolean exit(char[][] board,String word){
 int h = board.length,w = board[0].length;
 boolean[][] visted = new boolean[h][w];
 for(int i = 0;i<h;i++){
 for(int j = 0;j<w;j++){
 boolean flag = check(board,visted,i,j,word,0);
 if(flag){
 return true;
 }
 }
 }
 return false;
 }
 public boolean check(char[][] board,boolean[][]visted,int i,int j,String s,int k){
 if(board[i][j] != s.charAt(k)){
 return false;
 }else if(k == s.charAt(k)){
 return true;
 }
 visted[i][j] = true; //回溯选择
 int [][] directions = {{0,1},{0,-1},{1,0},{-1,0}}; //上下左右
 boolean result = false;
 //当前节点上下左右都尝试
 for(int[] dir : directions) {
 int newi = i + dir[0], newj = j + dir[1];
 if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) {
 if (!visted[newi][newj]) {
 boolean flag = check(board, visted, newi, newj, s, k + 1);
 if (flag) {
 result = true;
 break;
 }
 }
 }
 }
 visted[i][j] = false; //回溯剪枝
 return result;
 }
}
/*
class Solution {
 public boolean exist(char[][] board, String word) {
 int h = board.length, w = board[0].length;
 boolean[][] visited = new boolean[h][w];
 for (int i = 0; i < h; i++) {
 for (int j = 0; j < w; j++) {
 boolean flag = check(board, visited, i, j, word, 0);
 if (flag) {
 return true;
 }
 }
 }
 return false;
 }

 public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {
 if (board[i][j] != s.charAt(k)) {
 return false;
 } else if (k == s.length() - 1) {
 return true;
 }
 visited[i][j] = true;
 int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
 boolean result = false;
 for (int[] dir : directions) {
 int newi = i + dir[0], newj = j + dir[1];
 if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) {
 if (!visited[newi][newj]) {
 boolean flag = check(board, visited, newi, newj, s, k + 1);
 if (flag) {
 result = true;
 break;
 }
 }
 }
 }
 visited[i][j] = false;
 return result;
 }
}




 */