面试题 12. 矩阵中的路径

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(i, j, k):
            if k == len(word):
                return True
            if i < 0 or i >= m or j < 0 or j >= n or word[k] != board[i][j]:
                return False
            board[i][j] = ''
            ans = any(
                dfs(i + a, j + b, k + 1) for a, b in [[0, -1], [0, 1], [1, 0], [-1, 0]]
            )
            board[i][j] = word[k]
            return ans

        m, n = len(board), len(board[0])
        return any(dfs(i, j, 0) for i in range(m) for j in range(n))

class Solution {
    private char[][] board;
    private String word;
    private int m;
    private int n;

    public boolean exist(char[][] board, String word) {
        m = board.length;
        n = board[0].length;
        this.board = board;
        this.word = word;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (dfs(i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(int i, int j, int k) {
        if (k == word.length()) {
            return true;
        }
        if (i < 0 || i >= m || j < 0 || j >= n || word.charAt(k) != board[i][j]) {
            return false;
        }
        board[i][j] = ' ';
        int[] dirs = {-1, 0, 1, 0, -1};
        boolean ans = false;
        for (int l = 0; l < 4; ++l) {
            ans = ans || dfs(i + dirs[l], j + dirs[l + 1], k + 1);
        }
        board[i][j] = word.charAt(k);
        return ans;
    }
}

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function (board, word) {
    const m = board.length;
    const n = board[0].length;
    let dfs = function (i, j, k) {
        if (k == word.length) {
            return true;
        }
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word[k]) {
            return false;
        }
        board[i][j] = ' ';
        let ans = false;
        let dirs = [-1, 0, 1, 0, -1];
        for (let l = 0; l < 4; ++l) {
            ans = ans || dfs(i + dirs[l], j + dirs[l + 1], k + 1);
        }
        board[i][j] = word[k];
        return ans;
    };
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (dfs(i, j, 0)) {
                return true;
            }
        }
    }
    return false;
};

func exist(board [][]byte, word string) bool {
	m, n := len(board), len(board[0])
	var dfs func(i, j, k int) bool
	dfs = func(i, j, k int) bool {
		if k == len(word) {
			return true
		}
		if i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word[k] {
			return false
		}
		board[i][j] = ' '
		dirs := []int{-1, 0, 1, 0, -1}
		ans := false
		for l := 0; l < 4; l++ {
			ans = ans || dfs(i+dirs[l], j+dirs[l+1], k+1)
		}
		board[i][j] = word[k]
		return ans
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if dfs(i, j, 0) {
				return true
			}
		}
	}
	return false
}

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        for (int i = 0; i < board.size(); ++i)
            for (int j = 0; j < board[0].size(); ++j)
                if (dfs(i, j, 0, board, word))
                    return 1;
        return 0;
    }

    bool dfs(int i, int j, int k, vector<vector<char>>& board, string word) {
        if (k == word.size()) return 1;
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] != word[k]) return 0;
        vector<int> dirs = {-1, 0, 1, 0, -1};
        board[i][j] = ' ';
        bool ans = 0;
        for (int l = 0; l < 4; ++l)
            ans = ans || dfs(i + dirs[l], j + dirs[l + 1], k + 1, board, word);
        board[i][j] = word[k];
        return ans;
    }
};

function exist(board: string[][], word: string): boolean {
    const m = board.length;
    const n = board[0].length;
    const dfs = (i: number, j: number, k: number) => {
        if ((board[i] ?? [])[j] !== word[k]) {
            return false;
        }
        if (++k === word.length) {
            return true;
        }
        const temp = board[i][j];
        board[i][j] = ' ';
        if (
            dfs(i + 1, j, k) ||
            dfs(i, j + 1, k) ||
            dfs(i - 1, j, k) ||
            dfs(i, j - 1, k)
        ) {
            return true;
        }
        board[i][j] = temp;
        return false;
    };
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (dfs(i, j, 0)) {
                return true;
            }
        }
    }
    return false;
}

impl Solution {
    fn dfs(board: &mut Vec<Vec<char>>, chars: &Vec<char>, i: usize, j: usize, mut k: usize) -> bool {
        if board[i][j] != chars[k] {
            return false;
        }
        k += 1;
        if k == chars.len() {
            return true;
        }
        let temp = board[i][j];
        board[i][j] = ' ';
        if i != 0 && Self::dfs(board, chars, i - 1, j, k)
            || j != 0 && Self::dfs(board, chars, i, j - 1, k)
            || i != board.len() - 1 && Self::dfs(board, chars, i + 1, j, k)
            || j != board[0].len() - 1 && Self::dfs(board, chars, i, j + 1, k)
        {
            return true;
        }
        board[i][j] = temp;
        false
    }

    pub fn exist(mut board: Vec<Vec<char>>, word: String) -> bool {
        let m = board.len();
        let n = board[0].len();
        let chars = word.chars().collect::<Vec<char>>();
        for i in 0..m {
            for j in 0..n {
                if Self::dfs(&mut board, &chars, i, j, 0) {
                    return true;
                }
            }
        }
        false
    }
}

public class Solution {
    public bool Exist(char[][] board, string word) {
        int k = 0;
        for (int i = 0; i < board.Length; i++)
        {
            for (int j = 0; j < board[0].Length; j++)
            {
                if (dfs(board, word, i, j, k)) {
                    return true;
                }
            }
        }
        return false;
    }

    public bool dfs(char[][] board, string word, int i, int j, int k) {
        if (i > board.Length - 1 || i < 0 || j > board[0].Length - 1 || j < 0 || board[i][j] != word[k]) {
            return false;
        }
        if (k == word.Length - 1) {
            return true;
        }

        board[i][j] = '\0';
        bool res = dfs(board, word, i+1, j, k+1) || dfs(board, word, i, j+1, k+1) || dfs(board, word, i-1, j, k+1) || dfs(board, word, i, j-1, k+1);
        board[i][j] = word[k];
        return res;
    }
}