Tags » BF's

Surrounded Regions

Problem from leetcode Surrounded Regions

This is again a classical DFS/BFS problem. This time, we search from four edges, mark all accessible O to A, then for loop the whole matrix, mark remaining O to X and change A back to O. 565 more words


Sum Root to Leaf Numbers

Problem from leetcode Sum Root to Leaf Numbers

There is only one method to solve this problem: traverse the tree. For traversing one tree, we can either use BFS or DFS. 278 more words


Word Ladder II

Problem from leetcode Word Ladder II

This problem is similar to , this time we need to keep the path. Again we use BFS.

class Solution {
    vector<vector> findLadders(string beginWord, string endWord, unordered_set &wordList) {
        vector<vector > result;
        int length = beginWord.size();
        //this time we need to keep all intermediate words during the path
        queue<vector > tool;
        tool.push(vector(1, beginWord));
        bool found = false;
            //for expanding each level, we store the words used in this level
            vector usedWords;
            int size = tool.size();
            while(size > 0)
                vector tmp = tool.front(); tool.pop();
                string last = tmp;
                bool flag = false;
                for(int index = 0; index < length && !flag; ++index)
                    for(char c = 'a'; c <= 'z' && !flag; ++c)
                        string t = last;
                        t = c;
                        if(t == endWord)
                            found = true;
                            flag = true;
                        if(wordList.find(t) != wordList.end())
                            vector h = tmp;
            if(found) break;
            //we delete used words only after expand all path in this level
            for(int i = 0; i < usedWords.size(); ++i)
        return result;
… 13 more words

Word Ladder

Problem from leetcode Word Ladder

Just a simple glance, this problem should use BFS to find the result since need to find the shortest length. In order to avoid repeating use a word, we will delete the used word from wordList. 210 more words


Simple BFS


#include <iostream>
#include <queue>
#define MAX 100
using namespace std;

int Array = {
{0, 2, 1, 0, 0, 3},
{2, 0, 0, 0, 0, 5},
{1, 0, 0, 1, 3, 0},
{0, 0, 1, 0, 2, 0},
{0, 0, 3, 2, 0, 3},
{3, 5, 0, 0, 3, 0}
int V = 6;

// khai bao cac mang can thiet
int color, back;
queue<int> qlist;

void PrintPath(int u, int v, int back[])
if(u == v){
cout << v << " ";
// dua vao nut cha de tim duong di ngan nhat. 207 more words

"American Show-n-Tell" Part.2

Looking at myself across the mirror

Raising my right hand, then I raise left hand across the mirror.

Trying to parallel my purpose, but always opposite action across the mirror. 94 more words


BFS Application: word ladder

I’ve been recently practicing and sharpening python programming and realized python is extremely NEAT compared to other languages(C/C++, JAVA or C#). Also the running time is much faster than JAVA and C#. 621 more words