博客

BFS作为可以得出最短路径的暴力搜索方法，在很多问题上都是可以直接使用的。直接给自己一个模板方便之后使用。

		//一般来说是默认是一步的
 		int step = 1;
        Set<String> visited = new HashSet<>();
        Queue<String> q = new LinkedList<>();
        q.offer("0000");
        visited.add("0000");
        while(!q.isEmpty())
        {
            int sz = q.size();
            for(int i = 0; i < sz; i++)
            {
                String temp = q.poll();
                if(dead.contains(temp))
                    continue;
                if(temp.equals(target))
                    return step;
                for(int j = 0; j < 4; j++)
                {
                    String up = rollUp(temp, j);
                    if(!visited.contains(up))
                    {
                        q.offer(up);
                        visited.add(up);
                    }
                    String down = rollDown(temp, j);
                    if(!visited.contains(down))
                    {
                        q.offer(down);
                        visited.add(down);
                    }
                }       
            }
            step ++;
        }
        return -1;
    }