sonny玩妈妈的头绳 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>pets - 心有所宠

sonny玩妈妈的头绳

sonny玩妈妈的头绳# pets - 心有所宠

t*f2012-12-30 08:12

1 楼

万能的EBIZ啊，有么有朋友知道什么是Blended Leather？和普通的Leather有什么不同
，谢谢。

m*l2012-12-30 08:12

2 楼

了解这题DFS的话代码简洁而且大测试不超时。
就是想拿这题练习一下BFS的解法，自己吭哧吭哧写的代码超时了，不知道代码中的哪
一步太耗时？大家帮忙看一下，谢谢~
或者其他可以改进的地方大家也不妨指出~
代码如下：
public class Solution {

public static Queue queue = new LinkedList();
public boolean exist(char[][] board, String word) {
if (word.equals("") || word == null)
return true;
if (board == null || board.length == 0)
return false;
int row = board.length;
int col = board[0].length;
String tmp = word; // save complete word for repeated use
boolean[][] visited;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
word = tmp;
visited = new boolean[row][col]; // refresh visited at
beginning of every new iteration
if (board[i][j] == word.charAt(0)) {
word = word.substring(1);
if (word.length() == 0) return true;
Cell cell = new Cell(i, j);
queue.offer(cell);
visited[i][j] = true;
if (bfs(board, word, visited)) {
return true;
}
}
}
}
return false;
}
public boolean bfs(char[][] board, String word, boolean[][] visited) {
int[][] dir = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
while (!queue.isEmpty()) {
Cell tmp = queue.poll();
int x = tmp.row;
int y = tmp.col;
for (int k = 0; k < 4; k++) {
int i = x + dir[k][0];
int j = y + dir[k][1];
if (i >= 0 && j >= 0 && i < board.length && j < board[0].
length && board[i][j] == word.charAt(0) && !visited[i][j]) {
word = word.substring(1);
if (word.length() == 0) return true;
Cell cell = new Cell(i, j);
queue.offer(cell);
visited[i][j] = true;
}
}
}
return false;
}

static class Cell {
int row;
int col;
public Cell (int row, int col) {
this.row = row;
this.col = col;
}
}

}