50 回溯算法解单词搜索

问题描述：给定一个二维网格和一个单词构成，找出该单词是否存在于网格中。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中相邻单元格是哪些水平或垂直相邻的单元格，同一单元格的字母不允许被重复利用。

回溯算法求解：首先定义一个used二维数组用于表征当前哪些表格已经选取过，且每一步都有上下左右四种方式，而在每次加入的时候需要判断已加入的部分是否与字符串对应部分相等，若不相等则剪去该步。

public Boolean tranceBack(int [][]board,int i,int j,int[][]used,String s,int length)
{
if(length==s.length()){return? true;}
if(i>board.length||i<0||j>borad[0].length||j<0){return false;}
if(used[i][j]==false)
{
if(s.charAt(length)==borad[i][j])
{
used[i][j]=true;
if(tranceBack(board,i,j+1,used,s,length+1)){return true;}
if(tranceBack(board,i,j-1,used,s,length+1)){return true;}
if(tranceBack(board,i+1,j,used,s,length+1)){return true;}
if(tranceBack(board,i-1,j,used,s,length+1)){return true;}
used[i][j]=false;
}else
{
return false;
}

}else
{
return false;
}

}
public Boolean TranceBack(int board[][],String s)
{
Boolean[][]used=new Boolean[board.length][board[0].lenbgth];
for(int i=0;i<board.length;i++)
{
Arrays.fill(board[i],false);
}
for(int i=0;i<board.length;i++)
{
for(int j=0;j<board[i].length;j++)
{
if(tranceBack(board,i,j,used,s,0)){return true;}
}
}
return false;
}