題目要求
現(xiàn)在有一個(gè)二維數(shù)組，元素為字符。求能否在二維數(shù)組中得到一條通路連接的元素為給定的字符串鹉勒。
題目解析
思路一：
- 分析
這是典型的回溯算法乍炉。首先我們要定義一個(gè)與二位數(shù)組等大的boolean類(lèi)型的數(shù)組。用來(lái)表示元素是否被占用霍衫。
首先我們要找到一個(gè)元素等于給定字符串的首位字符，然后探索其上下左右是否等于給定數(shù)組的下一個(gè)元素。并沒(méi)被占用伞租。則，我們的函數(shù)就會(huì)從找到的點(diǎn)向四周延伸出去限佩，遇到不符合條件則停止葵诈，當(dāng)當(dāng)前節(jié)點(diǎn)的四個(gè)延伸都走不通，那么回到上一步祟同，對(duì)下一個(gè)符合條件的做檢測(cè)作喘。
- 代碼段
public static boolean hasPath (char[][] datas , String data) throws Exception {
int rows ;
int cols ;
if(datas == null || datas.length == 0 || data == null || data.length() == 0) {
throw new Exception("二維數(shù)組為空，不合法的參數(shù)") ;
}
rows = datas.length ;
cols = datas[0].length ;
visited = new boolean[rows][cols] ;
pathlength = 0 ;
for(int i = 0 ; i < rows ; i++ ) {
for(int j = 0 ; j < cols ; j++) {
if(hasPathCode(datas , rows , cols , i , j , data)) {
return true ;
}
}
}
return false ;
}
static int pathlength ;
static boolean[][] visited ;
public static boolean hasPathCode(char[][] datas , int rows , int cols , int row , int col , String data ) {
boolean hasPath = false;
if(pathlength == data.length()) {
return true ;
}
//如果此點(diǎn)符合條件晕城，那么對(duì)其四周進(jìn)行檢測(cè)
if( 0 <= row && row < rows && 0 <= col && col < cols && data.charAt(pathlength) == datas[row][col] && !(visited[row][col]) ) {
pathlength ++ ;
visited[row][col] = true ;
//檢查四周有沒(méi)有符合條件的路泞坦。
hasPath = hasPathCode(datas , rows , cols , row+1 , col , data)
||hasPathCode(datas , rows , cols , row , col+1 , data)
||hasPathCode(datas , rows , cols , row-1 , col , data)
||hasPathCode(datas , rows , cols , row , col-1 , data) ;
//另尋他路
if(!hasPath) {
pathlength -- ;
visited[row][col] = false ;
}
}
return hasPath ;
}
測(cè)試代碼
public static void main(String[] args) {
char[][] datas = {
{'a','s','d','f'},
{'z','x','c','v'},
{'q','w','e','r'},
{'z','x','c','v'}
} ;
char[][] datas1 = {
{'a','a','a','a'},
{'a','a','a','a'},
{'a','a','a','a'},
{'a','a','a','a'}
} ;
char[][] datas2 = {
{'a','s','d','f'}
} ;
String data = "dcxwe" ;
String data1 = "aaaaa" ;
String data2 = "fds" ;
try {
System.out.println( hasPath(datas, data) );
System.out.println("oooooooooooooooooooooooooooooooo");
System.out.println( hasPath(datas1, data1) );
System.out.println("oooooooooooooooooooooooooooooooo");
System.out.println( hasPath(datas2, data2) );
} catch (Exception e) {
e.printStackTrace();
}
}
運(yùn)行結(jié)果
true
oooooooooooooooooooooooooooooooo
true
oooooooooooooooooooooooooooooooo
true
