vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
     dict.insert(end);
     pre.clear();
     len.clear();
     queue<string> q;
     q.push(start);
     len[start] = 0;
     while(!q.empty()) {
         string s = q.front(), t = s;
         int d = len[s];
         q.pop();
         if (t == end)
             break;
         for(int i = 0; i < s.length(); i++) {
             int k = s[i]-'a';
             for(int j = 0; j < 26; j++) {
                 if( j != k) {
                     s[i] = 'a'+j;
                     if (dict.count(s)>0) {
                         if (len.count(s) == 0) {
                             len[s] = d+1;
                             pre[s].push_back(t);
                             q.push(s);
                         } else if(len[s] == d+1) {
                             pre[s].push_back(t);
                         }
                     }
                 }
             }
             s[i] = 'a'+k;
         }
     }
     ans.clear();
     tmp.assign(1, end);
     build(start, end);
     return ans;
 }

    /*
     * Recursivly explores the game board and add any solutions to validWords collection.
     */
    void Boggle::explore(string word, int x, int y, unordered_set<int>& visited){

        //Add letter contained in this cell to word.
        word.push_back(board.get(y, x));

        //If our word is a valid prefix it is worth to continue, otherwise we return.
        if(lexicon.containsPrefix(word)){

            //If word is acceptable we add it to validWords collection.
            if(word.length() >= MIN_WORD_LENGTH && !alreadyFound(word) && lexicon.contains(word)){

                cpuScore += scoreFor(word);
                cpuWords.insert(word);
            }

            //Convert coordinates to index in order to more easily store them as visited.
            int currentIndex = x + y * BOARD_WIDTH;
            visited.insert(currentIndex);

            //Check all possible neighbours, exploring those who are withing bounds.
            for(int ny = y - 1; ny <= y + 1; ny++){
                for(int nx = x - 1; nx <= x + 1; nx++){
                    if(board.inBounds(ny, nx)){
                        if(visited.count(nx + ny * BOARD_WIDTH) == 0){

                                explore(word, nx, ny, visited);
                        }
                    }
                }
            }

            //Erase cell from visited collection as we are backtracking.
            visited.erase(currentIndex);
        }

        return;
    }

    int ladderLength(string start, string end, unordered_set<string> &dict) {
        deque<string> pop_from;
        deque<string> push_to;
        int total_dist = 1;
        // init
        pop_from.push_back(start);

        while(!pop_from.empty()) {
            while (!pop_from.empty()) {
                string& orig = pop_from.front();
                string node = pop_from.front();
                int dist = 0;
                for (int i = 0; i < node.length() && dist < 2; i++) {
                    if (node[i] != end[i]) {
                        ++dist;
                    }
                }
                if (dist <= 1) {
                    return total_dist + dist;
                }
                for (int i = 0; i < orig.length(); ++i) {
                    node = orig;
                    for (char j = 'a'; j <= 'z'; ++j) {
                        node[i] = j;
                        if (dict.count(node) > 0) {
                            push_to.push_back(node);
                            dict.erase(node);
                        }
                    }
                }
                pop_from.pop_front();
            }
            pop_from.swap(push_to);
            ++total_dist;
        }
        return 0;
    }

		bool wordBreak(string s, unordered_set<string> &dict) {
			int len = (int)s.size();
			int *st = new int[len+1];

			/*
			printf("%s\n", s.c_str());
			for (unordered_set<string>::iterator usit = dict.begin(); usit != dict.end(); ++usit)
			{
				printf("%s\n", usit->c_str());
			}
			*/	

			memset(st, 0, sizeof(int) * (len+1));
			st[0] = 1;
			unordered_set<string>::iterator usit = dict.begin();

			for (int i = 1; i <= len; ++i)
			{
				for (usit = dict.begin(); usit != dict.end(); ++usit)
				{
					int cur_len = (int)usit->size();
					int dis = i - cur_len;
					if (dis < 0) continue; //too short, impossible
					const char *start = s.c_str() + dis;

					if (st[dis] == 1 && strncmp(start, usit->c_str(), cur_len) == 0)
					{
						st[i] = 1;
						break;
					}
				}
			}

			bool res = st[len] == 1;
			delete[] st;
			return res;
		}

	void WordBreak(string s, string curStr, unordered_set<string> & dict, unordered_set<string>& cache, vector<string> & res)
	{
		if (s.length() == 0)
		{
			res.push_back(curStr);
			return;
		}
		else
		{
			for (int i = 1; i <= s.length(); i++)
			{
				string str = s.substr(0, i);
				if (dict.count(str) != 0 && cache.count(s.substr(i)) == 0)
				{
					int size = res.size();
					WordBreak(s.substr(i), curStr.length() > 0 ? curStr + " " + str : str, dict, cache, res);
					if (res.size() == size)
					{
						cache.insert(s.substr(i));
					}
				}
			}
		}
	}

        vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
            int len = s.size();
            vector<bool> canBreak(len+1);
            vector<int> idxes;
            idxes.push_back(0);
            canBreak[0] = true;
            for (int i=1; i<=len; ++i)
                for (int j=i-1; j>=0; --j)
                    if (canBreak[j] && wordDict.count(s.substr(j, i-j))) {
                        canBreak[i] = true;
                        idxes.push_back(i);
                        break;
                    }
            if (!canBreak[len]) return {};

            int idxLen = idxes.size();
            vector<vector<string>> breaks(idxLen+1);
            breaks[0].push_back({""});
            string word;
            int idx1, idx2;
            for (int i=1; i<=idxLen; ++i) {
                for (int j=0; j<i; ++j) {
                    idx1 = idxes[j]; idx2 = idxes[i];
                    word = s.substr(idx1, idx2-idx1);
                    if (wordDict.count(word))
                        for (auto &w : breaks[j])
                            breaks[i].push_back(w + word + ' ');
                }
            }

            vector<string> res;
            for (auto &w : breaks[idxLen]) {
                res.push_back(w.substr(0, w.size()-1));
            }
            return res;
        }

    bool wordBreak(string s, unordered_set<string> &dict) {

        if(  s.length() == 0 ){

            return true;
        }
        bool flag[1000];
        memset(flag, false,sizeof(flag));
        flag[0] = true;

        for( int i = 0 ; i < s.length(); i++){

            for( int j = 0; j <= i; j++){

                if( flag[j] && ( dict.find( s.substr(j,i +1 - j)) != dict.end())){
                    flag[i + 1] = true;

                }
            }
        }

        return flag[s.length()];

    }

 bool wordBreak(string s, unordered_set<string>& wordDict) {
     int n = s.size();
     if (n == 0) return false;
     vector<bool> dp(n + 1, false); // dp[i+1] : 0~i is true
     dp[0] = true;
     for (int i = 0; i < n; i++) {
         for (int j = i; j >= 0; j--) {
             if (dp[j] && wordDict.count(s.substr(j, i-j+1)) > 0) {
                 dp[i+1] = true;
                 break; // no need for further steps
             }
         }
     }
     return dp[n];
 }

int bfs(string start, string end, unordered_set<string> &dict, unordered_map<string,int> &level) 
{
	int n = dict.size();
	queue<string> q;
	q.push(start);
	int dist = 0;
	queue<string> q1;
	level[start] = 0;
	while(q.size() || q1.size())
	{
		if (q.size() == 0)
		{
			dist++;
			q = q1;
			q1 = queue<string>();
		}
		string str = q.front();
		q.pop();
		if (str == end)
			return dist;
		for ( int i = 0; i < str.size(); i++)
			for ( char c = 'a'; c <= 'z'; c++)
			{
				if (str[i] == c) continue;
				string str1 = str;
				str1[i] = c;
				if ( (dict.count(str1) || str1 == end ) && !level.count(str1))
				{
					q1.push(str1);
					level[str1] = dist + 1;
				}

			}	
	}
	return 0;
}

    vector<vector<string> > findLadders(string start, string end, unordered_set<string> &dict) 
    {
        vector<vector<string> > result;

        map<string,Node*> nodes;
        Node nStart;
        nStart.name = start;

        Node nEnd;
        nEnd.name = end;
        nodes[start] = &nStart;
        for (std::unordered_set<string>::iterator i = dict.begin(); i != dict.end(); ++i)
        {
            Node* tmp = new Node();
            tmp->name = *i;
            nodes[*i] = tmp;
        }
        nodes[end] = &nEnd;
        dict.insert(end);
        dict.insert(start);


        nodes[start]->val = 1;
        innerSearch(nodes[start],dict,nodes);
        int minValue = nodes[start]->val == INT_MAX ? 0 : nodes[end]->val; 
        if ( minValue > 0 )
        {
            //printf("size:%ld\n", nodes[start]->nexts.size());
            vector<string> parent;
            parent.push_back(start);
            innerCreate(nodes[start],1,minValue,parent,result);
        }
        return result;


    }

void _gameData::addEnemyMaskPlus1(unordered_set<pos>& poses, pos rc){
  float sqrtfar2=sqrt(ar2);
  int maskcnt=0;
  for(int row=-4; row<=4; row++){
    for(int col=-4; col<=4; col++){
      float oedist=sqrt(euclideanDist2(0,0,row,col,rows,cols));
      //if(sqrtfar2+1<oedist and oedist<=sqrtfar2+2){
      if(oedist<=sqrtfar2+2){
        poses.insert(pos(wrap(rc.row+row, rows), wrap(rc.col+col,cols)));
        maskcnt++;
      }
    }
  }
  //LOG("added " << maskcnt << " mask tiles");
};

 bool wordBreak(string s, unordered_set<string> &dict) {
     if (s.empty()) return false;
     int N = s.size();
     vector<bool> dp(N + 1, false);
     dp[0] = true;
     for (int j = 1; j <= N; j++) {
         for (int i = 0; i < j; i++) {
             if (dict.count(s.substr(i, j - i)) && dp[i]) {
                 dp[j] = true;
                 break;
             }
         }
     }
     return dp[N];
 }

 void buildMap(const unordered_set<string>& dict) {
     vdict.clear();
     unordered_map<string, int> unmap;
     for (auto iter = dict.begin(); iter != dict.end(); iter++) {
         unmap[*iter] = vdict.size();
         vdict.push_back(*iter);
     }
     
     map.clear();
     map.resize(vdict.size());
     for (size_t i = 0; i < vdict.size(); i++) {
         string word = vdict[i];
         for (size_t j = 0; j < word.size(); j++) {
             for (char c = 'a'; c <= 'z'; c++) {
                 if (c == vdict[i][j]) continue;
                 word[j] = c;
                 if (unmap.count(word)) {
                     map[i].push_back(unmap[word]);
                 }
                 word[j] = vdict[i][j];
             }
         }
     }
 }

 void dfs(string s, int index, vector<string> &result, string &eachResult, vector<bool> &possible, unordered_set<string> &dict) {
     if (index == s.size()) {
         eachResult.resize(eachResult.size() - 1);
         result.push_back(eachResult);
         return;
     }
     
     for (int i = 1; i <= (int)s.size() - index; i++) {
         string tmp = s.substr(index, i);
         if (dict.find(tmp) != dict.end() && possible[index + i]) {
             string origin = eachResult;
             eachResult.append(tmp).append(" ");
             int beforeDFS = (int)result.size();
             dfs(s, index + i, result, eachResult, possible, dict);
             if (result.size() == beforeDFS) {
                 possible[index + i] = false;
             }
             
             eachResult = origin;
         }
     }
     
     return;
 }

/* remove overlaps that are duplicated in vector left, and spot sequences that should be remove in next pass because they reached their best overlap with a duplicated sequence */
vector<edge> removeNotSinglesInLeft(const vector<edge>& vect, unordered_set<string>& seqsToRemoveInPref, unordered_set<string>& seqsToRemoveInSuff){
	vector<edge> vectResult;
	uint i(0);
	bool remove(false);
	while (i < vect.size()){
		if (i == 0){
			if (vect[i].sequence != vect[i+1].sequence){
				vectResult.push_back(vect[i]);
			} else {
				remove = true;
			}
		} else if (i == vect.size()-1){
			if (vect[i].sequence != vect[i-1].sequence){
				vectResult.push_back(vect[i]);
			} else {
				remove = true;
			}
		} else {
			if (vect[i].sequence != vect[i+1].sequence and vect[i].sequence != vect[i-1].sequence){
				vectResult.push_back(vect[i]);
			} else {
				remove = true;
			}
		}
		if (remove == true){
			if (vect[i].canonical == true){
				seqsToRemoveInSuff.insert(vect[i].sequence);
			} else {
				seqsToRemoveInPref.insert(vect[i].sequence);
			}
		}
		++i;
		remove = false;
	}
	return vectResult;
}

 void helper(string beginWord, string endWord, unordered_set<string> wordList, int& minLength, vector<string>& ladder, vector<vector<string>>& res) {
     if (beginWord == endWord || isIntermediate(beginWord, endWord)) {
         if (isIntermediate(beginWord, endWord)) {
             ladder.push_back(endWord);
         }
         if (ladder.size() == minLength) {
             res.push_back(ladder);
         } else if (ladder.size() < minLength) {
             res.clear();
             res.push_back(ladder);
             minLength = ladder.size();
         }
         return;
     }
     for (auto it = wordList.begin(); it != wordList.end(); ++it) {
         if (isIntermediate(beginWord, *it)) {
             ladder.push_back(*it);
             unordered_set<string> newWordList = wordList;
             newWordList.erase(newWordList.find(*it));
             helper(*it, endWord, newWordList, minLength, ladder, res);
         }
     }
     return;
 }

bool StringProduction(string src, string dst, unordered_set<string> dico, list<string>* prod_seq)
{
	if (dico.find(src) == dico.end() || dico.find(dst) == dico.end())
		return false;

	map<string, string> parents;
	unordered_set<string> processed;
	queue<string> discovered;
	
	//init the bfs
	discovered.push(src); 
	parents[src] = "";
	while (!discovered.empty())
	{
		string current = discovered.front();discovered.pop();
		processed.insert(current);
		list<string> neighbours = GetNeighbours(current, dico);
		for (string s : neighbours)
		{
			if (processed.find(s) == processed.end())
			{
				parents[s] = current;
				discovered.push(s);
			}
		}		
	}
	if (processed.find(dst) == processed.end())
		return false;
	
	while (dst!="")
	{
		prod_seq->push_front(dst);
		dst = parents[dst];
	}
	return true;
}

    int ladderLength(string start, string end, unordered_set<string> &dict) {
	int length = 2, count = 1, neighb = 0;
	unordered_set<string> visited;
	queue<string> level;
	level.push(start);
	visited.insert(start);
	while(!level.empty())
	{
	    string curr = level.front();
	    level.pop();
	    --count;
	    for(int i = 0; i < curr.size(); ++i)
	    {
		for(int j = 0; j < 26; ++j)
		{
		    string next = curr;
		    next[i] = 'a' + j;
		    if(next == end)
			return length;
		    if(dict.find(next) != dict.end() && visited.find(next) == visited.end())
		    {
			++neighb;
			level.push(next);
			visited.insert(next);
		    }
		}
	    }
	    if(count == 0)  // new level starts
	    {
		++length;
		count = neighb;
		neighb = 0;
	    }
	}
	return 0;
    }

    int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
        queue<string> q;
        int s = beginWord.size();
        int r = 1;
        q.push(beginWord);
        while  (!q.empty()) {
            cout << " -+-+-+-+-+-+-+ " << endl;
            int num = q.size();
            bool found = false;
            for (int i = 0; i < num; i++) {
                    string tmp = q.front();
                    cout << "tmp:" << tmp << endl;
                    q.pop();
                    for (int k = 0; k != s; k++) {
                        char c = tmp[k];
                        for (int l = 0; l < 26; l++) {
                            tmp[k] = 'a'+l;
		            unordered_set<string>::iterator it;
                            it = wordList.find(tmp);
                            if (it != wordList.end()) {
                                if (*it == endWord) {
			            cout << *it << ",";
                	            return r+1;
                                } else {
                                    q.push(tmp);
                                    wordList.erase(it);
                                }
                            }
                        }
                        tmp[k] = c;
                    }
            }
            r++;
        }
        return 0;
    }

 int ladderLength(string start, string end, unordered_set<string> &dict) {
     dict.insert(end);
     queue<pair<string,int>> q;
     q.push(make_pair(start,1));
     while(!q.empty()) {
         string s = q.front().first;
         int len = q.front().second;
         if(s==end) return len;
         q.pop();
         vector<string> neighbors = findNeighbors(s, dict);
         for(int i=0; i<neighbors.size(); i++) 
             q.push(make_pair(neighbors[i],len+1));
     }
     return 0;
 }