**トピックの説明:** ある文字列のすべての文字を含む経路が行列内に存在するかどうかを判定する関数を設計してください。パスは行列の任意のグリッドから開始することができ、各ステップは行列の左、右、上、または下に1グリッド移動することができます。パ ス が行列内のセルを通過 し た と き は、 そのセルに再び進入す る こ と はで き ません。 
問題解決のアイデア
行列を繰り返し、最初の文字がstrである経路を見つける。[0]同一行列要素m；
mに隣接する上、下、左、右の4つの文字を反復する。[1]同じ文字なら、その文字が次の横切りの出発点となる；
到達できない場合は、前のマスに戻って縦断し直す。
経路の重複を避けるために、移動した行列要素を記録する経路の配列が必要である。
class Solution {
public boolean exist(char[][] board, String word) {
//if(board==null||board.length==0||board[0].length==0||word==null||word.equals("")){
// return false;
//}
boolean[][] isVisited=new boolean[board.length][board[0].length];
for(int i=0;i<board.length;i++){
for(int j=0;j<board[i].length;j++){
if(solve(board,word,i,j,isVisited,0)){
//状況を見つける
return true;
}
}
}
return false;
}
private boolean solve(char[][] board,String word,int x,int y,boolean[][] isVisited,int index){
//アウトオブバウンズの処理と、1マスに1回しか入れないこと
if(x<0||x>=board.length||y<0||y>=board[0].length||isVisited[x][y]){
return false;
}
//ある位置にマッチすることは条件を満たさない
if(word.charAt(index)!=board[x][y]){
return false;
}
//マッチに成功する
if(index==word.length()-1){
return true;
}
isVisited[x][y]=true; // [x][y]前進、後退、左右の動きをする 説明[x][y]訪問した
boolean res=solve(board,word,x+1,y,isVisited,index+1)||
solve(board,word,x-1,y,isVisited,index+1)||
solve(board,word,x,y+1,isVisited,index+1)||
solve(board,word,x,y-1,isVisited,index+1);
isVisited[x][y]=false;// の組に等しい。[x][y]この位置でバックトラックする
return res;
}
}
class Solution {
public boolean exist(char[][] board, String word) {
if (board == null || board[0] == null || board.length == 0 || board[0].length == 0 || word == null || word.equals("")) {
return false;
}
boolean[][] isVisited = new boolean[board.length][board[0].length];
char[] chs = word.toCharArray(); //文字列を文字の配列に変換する
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == chs[0]) {
if (bfs(board, i, j, isVisited, chs, 0)) return true;
}
}
}
return false;
}
private boolean bfs(char[][] board, int i, int j, boolean[][] isVisited, char[] chs, int index) {
if (index == chs.length) {
return true;
}
if (i < 0 || j < 0 || i == board.length || j == board[0].length || isVisited[i][j] || board[i][j] != chs[index]) {
return false;
}
isVisited[i][j] = true;
boolean res = bfs(board, i + 1, j, isVisited, chs, index + 1)
|| bfs(board, i - 1, j, isVisited, chs, index + 1)
|| bfs(board, i, j + 1, isVisited, chs, index + 1)
|| bfs(board, i, j - 1, isVisited, chs, index + 1);
isVisited[i][j] = false;
return res;
}
}
char[ ] chs = word.toCharArray(); ナレッジ・ポイント： //文字列を文字配列に変換
文字列のlengthとlength()の違いについて文字列配列はlength、文字列はlengthであることに注意
13.ロボットの可動範囲
**トピックの説明：** 床の上に m 行 n 列の正方形のグリッドがあります。ロボットは座標0,0のマス目から動き出し、左右上下の4方向に1マスずつしか移動できませんが、行と列の座標の桁数の和がkより大きいマス目には入ることができません。 例えばkが18のとき、3+5+3+7=18なのでロボットは正方形のマスに入ることができますが、3+5+3+8=19なのでロボットは正方形のマスに入ることができません。
問題解決のアイデア
はじめからスタートし、各ステップが成功するごとに現在位置を真としてマークし、次に現在位置から4方向すべてを探索する。，
現在の位置に戻る+ 4それぞれの方向に探索された値の和
探索するとき、ある地点に到達可能かどうかを判断する基準は次のような場合である：
---点が行列の内側にあるとき
---まだ到達していない点がある；
---点がLIMIT制約を満たすとき
public class Solution {
public int movingCount(int threshold, int rows, int cols)
{
boolean[][] isVisited =new boolean[rows][cols]; //ロボットが何度もマスに入らないようにトレーステーブルを歩く
return solve(0,0,rows,cols,isVisited,threshold);
}
private int solve(int x, int y, int rows, int cols, boolean[][] isVisited, int threshold) {
if(x<0||y<0||x>=rows||y>=cols||isVisited[x][y]||(getDigitSum(x)+getDigitSum(y))>threshold){
return 0;
}
int count=0;
isVisited[x][y]=true; //現在のマスに入り、再入場を防ぐためにトレーステーブルを真と記録する。
count=1+solve(x+1,y,rows,cols,isVisited,threshold)+ //1現在のマスに1カウントで入ったことを示す
solve(x-1,y,rows,cols,isVisited,threshold)+
solve(x,y+1,rows,cols,isVisited,threshold)+
solve(x,y-1,rows,cols,isVisited,threshold);
return count;
}
//座標桁の和を計算する
public int getDigitSum(int number){
int sum = 0;
//1桁目を足し、次に10桁目を足す。
while(number != 0){
sum += number % 10; //余りをとる。=423,3のバランスをとる。
number /= 10; //商をとる，423/10=42，つまり、数字を足してから残りの数字を数える。
}
return sum;
}
}
