首页 > 其他 > 详细

Word Search

时间:2014-05-26 01:23:56      阅读:383      评论:0      收藏:0      [点我收藏+]

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

说实话这题做的挺瞎的,题目挺简单,DFS呗,用递归做可能根本用不着写这么麻烦,就是怕递归超时才转成非递归,结果写的巨麻烦,直接贴代码吧,想看的看一看就好了。

bubuko.com,布布扣
 1 public boolean exist(char[][] board, String word) {
 2         int grid[][] = new int[board.length][board[0].length];
 3         for (int i = 0; i < board.length; i++) {
 4             for (int j = 0; j < board[0].length; j++) {
 5                 if (word.charAt(0) == board[i][j]) {
 6                     grid[i][j] = 1;
 7                     Stack<Info> stack = new Stack<Info>();
 8                     stack.push(new Info(i, j, 0, 0, 0));
 9                     while (!stack.empty()) {
10                         Info info = stack.pop();
11                         if (info.pos == word.length() - 1) {
12                             return true;
13                         }
14                         if(info.time==4){
15                             grid[info.i][info.j]=0;
16                             continue;
17                         }
18                         if (info.time<1&&info.direct != 1
19                                 && info.j > 0
20                                 && grid[info.i][info.j - 1] == 0
21                                 && word.charAt(info.pos + 1) == board[info.i][info.j - 1]) {
22                             info.time=1;
23                             stack.push(info);
24                             stack.push(new Info(info.i, info.j - 1, 2,
25                                     info.pos + 1,0));
26                             grid[info.i][info.j - 1] = 1;
27                         } else if (info.time<2&&info.direct != 2
28                                 && info.j < board[0].length - 1
29                                 && grid[info.i][info.j + 1] == 0
30                                 && word.charAt(info.pos + 1) == board[info.i][info.j + 1]) {
31                             info.time=2;
32                             stack.push(info);
33                             stack.push(new Info(info.i, info.j + 1, 1,
34                                     info.pos + 1,0));
35                             grid[info.i][info.j + 1] = 1;
36                         } else if (info.time<3&&info.direct != 3
37                                 && info.i > 0
38                                 && grid[info.i - 1][info.j] == 0
39                                 && word.charAt(info.pos + 1) == board[info.i - 1][info.j]) {
40                             info.time=3;
41                             stack.push(info);
42                             stack.push(new Info(info.i - 1, info.j, 4,
43                                     info.pos + 1,0));
44                             grid[info.i - 1][info.j] = 1;
45                         } else if (info.time<4&&info.direct != 4
46                                 && info.i < board.length - 1
47                                 && grid[info.i + 1][info.j] == 0
48                                 && word.charAt(info.pos + 1) == board[info.i + 1][info.j]) {
49                             info.time=4;
50                             stack.push(info);
51                             stack.push(new Info(info.i + 1, info.j, 3,
52                                     info.pos + 1,0));
53                             grid[info.i + 1][info.j] = 1;
54                         } else {
55                             info.time=4;
56                             stack.push(info);
57                         }
58                     }
59                     grid[i][j] = 0;
60                 }
61             }
62         }
63         return false;
64     }
View Code

Info是用于记录状态信息的结构,i,j表示横纵坐标,pos表示与word的第几个相匹配,direct表示上一个匹配在这个匹配的哪个方向,time是当前点已经判断了那些下一步的方向。

bubuko.com,布布扣
 1 class Info {
 2     int i;
 3     int j;
 4     int direct;
 5     int pos;
 6     int time;
 7 
 8     Info() {
 9         i = 0;
10         j = 0;
11         direct = 0;
12         pos = 0;
13         time = 0;
14     }
15 
16     Info(int i, int j, int dierct, int pos, int time) {
17         this.i = i;
18         this.j = j;
19         this.direct = dierct;
20         this.pos = pos;
21         this.time = time;
22     }
23 
24     public String toString() {
25         return "" + i + " " + j + " " + direct + " " + pos+" "+time;
26     }
27 }
View Code

bubuko.com,布布扣

Word Search,布布扣,bubuko.com

Word Search

原文:http://www.cnblogs.com/apoptoxin/p/3749780.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!