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, 5));
      }
      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(min(3, state.first + state.second),
    			max(state.second - (3 - state.first), 0));
      }
      if (state.first > 0 && state.second < 4) {
        newStates.push_back(min(4, state.second + state.first),
    			max(state.first - (4 - state.second), 0));
      }

      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.