I think that the function that computes new states could be simplified in this way:
vector <pair<int,int> > newStatesSet(pair<int,int> state){
//generating all possible states from a given initial state
vector<pair<int,int> > newStates;
if (state.first < 3) {
newStates.push_back(make_pair(3, state.second));
}
if (state.second < 4) {
newStates.push_back(make_pair(state.first, 4));
}
if (state.first > 0) {
newStates.push_back(make_pair(0, state.second));
}
if (state.second > 0) {
newStates.push_back(make_pair(state.first, 0));
}
if (state.second > 0 && state.first < 3) {
newStates.push_back(make_pair(std::min(3, state.first + state.second),
std::max(state.second - (3 - state.first), 0)));
}
if (state.first > 0 && state.second < 4) {
newStates.push_back(make_pair(std::max(state.first - (4 - state.second), 0),
std::min(4, state.second + state.first)));
}
return newStates;
}
Note that with this function a new state is generated from the previous state by considering a single operation. So, for instance, from the state (0, 0) it produces (3, 0) and (0, 4), but not (3, 4) (which will be generated later) as in your function. I think that this reflect more correctly the idea that each state is derived from the previous one with a single step.