0

i run this program and it gives the runtime error

" Runtime error: exit code is -1073741819 ".

can someone plz tell me why tis error occurs and how to rectify it?

the program is finding the word ladder (length of the shortest chain to reach the target word) . i.e Given a dictionary, and two words ‘start’ and ‘target’ (both of same length). Find length of the smallest chain from ‘start’ to ‘target’ if it exists, such that adjacent words in the chain only differ by one character and each word in the chain is a valid word i.e., it exists in the dictionary. It may be assumed that the ‘target’ word exists in dictionary and length of all dictionary words is same.

#include<bits/stdc++.h>
using namespace std;

string dic[] = {"POON", "PLEE", "SAME", "POIE", "PLEA", "PLIE", "POIN"};

int n = sizeof(dic)/sizeof(dic[0]);

set<string> graph;

struct word
{
    string s;
    int d;
};

bool isAdj(string &s , string &t)
{
    int count = 0;

    for(int i=0; i<s.length() && i<t.length(); i++)
       if(s[i] != t[i])
          count++;

    return (count == 1);      
}

int shortestPath(string s , string d)
{
    queue<word> que;

    word source = {s , 0};

    que.push(source);

    word cur;
    //string t = "PLEA";
    while(!que.empty())
    {
        cur = que.front();
        if(cur.s == d)
           break;

        for(string t : graph)
        {
            if(isAdj(cur.s , t))
            {
                word temp = {t, cur.d + 1};

                que.push(temp);
                graph.erase(t);
            }
        }

        que.pop();

    }

    if(cur.s == d)
        return cur.d;
  return 0;
}

main()
{

    for(int i=0; i<n; i++)
        graph.insert(dic[i]);

    cout<<"  "<<shortestPath("TOON" , "PLEA")   ; 
}

the question link is here http://www.geeksforgeeks.org/word-ladder-length-of-shortest-chain-to-reach-a-target-word/

thanks in advance.

Manvir
  • 769
  • 1
  • 7
  • 15
AJAY HAYAGREEVE
  • 168
  • 10
  • 3
    [Don't use ranged-for on a collection you modify during enumeration](http://stackoverflow.com/questions/10360461/removing-item-from-vector-while-in-c11-range-for-loop). – WhozCraig May 03 '17 at 06:04
  • but even if i use for(auto it = graph.begin(); it != graph.end(); it++) , the same runtime error is coming. – AJAY HAYAGREEVE May 03 '17 at 08:05
  • 3
    i linked that answer for a reason, and you would do well to read the selected answer. What you're doing is *still* wrong. Look closely at the *proper* example of how to perform iterator based enumeration with potential container item erasure in the [selected answer](http://stackoverflow.com/a/10360466/1322972) of the question I posted. There should be no increment-statement in the for-loop construct. there will be an erase **or** an increment within the *body* of the loop. Better still, recode it as a `while` and mimic the linked behavior. – WhozCraig May 03 '17 at 08:18
  • yeah worked. Thanks – AJAY HAYAGREEVE May 03 '17 at 17:45

1 Answers1

0

The comments have a major good point.

However, it misses another issue - you don't have to edit the graph in that loop.

list<string> foundStrings;
for(string t : graph)
        {
            if(isAdj(cur.s , t))
            {
                foundStrings.push_back(t);
            }
         }
for(string t: foundStrings) {
   word temp = {t, cur.d + 1};
   que.push(temp);
   graph.erase(t);
}

(There should probably be some error handling as well.)

Basically: If you are changing a sequence while you are iterating over it you have to take extra pre-cautions and cannot use C++11 style, but the best option is to not modify it at that time - the second option is to use iterators and take special care.

Hans Olsson
  • 11,123
  • 15
  • 38
  • The OP's code finds multiple "adjacent" strings, and queues all of them. Your code only uses the last (or first with the break) it finds. depending on the order the OP's example goes into the set, it won't find the depth. – Caleth May 03 '17 at 11:27
  • I changed the answer to handle multiple matches. – Hans Olsson May 03 '17 at 11:44