**The missionaries and cannibals**

The missionaries and cannibals

when exploring solution of this problem , I once took two different way. one is BFS:

#include<queue>
#include<iostream>
#include<cstring>
using namespace std;
int m, n;
int closed[1010][1010][2];
struct State{
    int m, c;
    int dep;
    int boat;
};
queue<State> q;
int bfs(State s){
    if(s.m == 0 && s.c == 0){
        return s.dep;
    }
    if(closed[s.m][s.c][s.boat] == 1)
        return -1;
    closed[s.m][s.c][s.boat] = 1;
    if(s.boat == 1){
        for(int i = n; i >= 1; i--){
            if(i > s.m + s.c)
                continue;
            for(int j = i; j >= 0; j--){
                if(j > s.c || i-j > s.m)
                    continue;
                if(j != i && j > i-j)
                    continue;
                if(s.m-(i-j) != 0 &&  (s.m-(i-j) != s.c - j)  &&  s.m-(i-j) != m)
                    continue; 
                if(closed[s.m-(i-j)][s.c-j][0] == 1)
                    continue;
                if(s.m -(i-j) == 0 && s.c - j == 0)
                    return s.dep +1;
                State next;
                next.boat = 0;
                next.m = s.m-(i-j);
                next.c = s.c - j;
                next.dep = s.dep+1;
                q.push(next);
            }
        }
    }else{
        for(int i = 1; i <= 2; i++){
            if(i > 2 * m - s.m -s.c)
                continue;
            for(int j = i; j >= 1; j--){
                if(j > m - s.c || i - j > m - s.m)
                    continue;
                if(j != i && j > i-j)
                    continue;
                if(m - s.m-(i-j) != 0 &&  (m - s.m-(i-j) != m - s.c - j) &&  s.m != 0)
                    continue; 
                if(closed[s.m+(i-j)][s.c+j][1] == 1)
                    continue;
                State next;
                next.boat = 1;
                next.m = s.m+(i-j);
                next.c = s.c + j;
                next.dep = s.dep+1;
                q.push(next);
            }
        }
    }
    return -1;
}
int main(){
    cin >> m >> n;
    State initial;
    initial.c = initial.m = m;
    initial.boat = 1;
    initial.dep = 0;
    q.push(initial);
    memset(closed, 0, sizeof(closed));
    int ans = -1;
    State s;
    while(!q.empty()){
        s = q.front();
        q.pop();
        ans = bfs(s);
        if(ans != -1){
            break;
        }
    }
    cout << ans;
    return 0;
}

that is , int a closed node-set to record whether i've searched this node , use a queue of
state as open node-set to those appeared but I've never searched , take board-first logic

another is Interative DEEPENING:

#include<iostream>
#include<stack>
struct nowstt
{
    int dir,tme;
    int wo[3],sh[3];
};
using namespace std;
int m=1000,n=100;
bool checkstt(nowstt & kk,int wo,int sh)
{
    if((kk.sh[0]>=kk.wo[0]||kk.sh[0]==0)&&(kk.sh[1]>=kk.wo[1]||kk.sh[1]==0)&&((kk.sh[kk.dir]+sh)>=(kk.wo[kk.dir]+wo)||(kk.sh[kk.dir]+sh)==0))
    {
        kk.sh[kk.dir]+=sh,kk.wo[kk.dir]+=wo;
        kk.sh[2]=sh,kk.wo[2]=wo;
        kk.tme++;
        kk.dir=(kk.dir+1)%2;
        return 1;
    }
    else return 0;
}
int revcio(int deps,stack<nowstt> & k1)
{
    if(k1.top().tme>deps) 
    {
        return 0;
    }
    nowstt pp=k1.top();
    for(int wo=0;wo<=pp.wo[(pp.dir+1)%2]&&wo<=n/2;wo++)
    {
        nowstt ppp=pp;
        if(wo!=0)
        {
            if(wo==ppp.wo[2]&&ppp.sh[2]==0) continue;
        ppp.wo[(pp.dir+1)%2]-=wo;
        if(checkstt(ppp,wo,0))
        {
            if(ppp.sh[0]==0&&ppp.wo[0]==0) return ppp.tme-1;
            k1.push(ppp);
            int y=revcio(deps,k1);
            if(y) return y;
            k1.pop();
        }
        }
        for(int sh=wo;sh<=pp.sh[(pp.dir+1)%2]&&(sh+wo)<=n;sh++)
        {
            if(wo==0&&sh==0) continue;
            if(wo==pp.wo[2]&&pp.sh[2]==sh) continue;
            if(!(sh<=pp.sh[(pp.dir+1)%2]&&(sh+wo)<=n))
            ppp=pp;
            ppp.wo[(pp.dir+1)%2]-=wo,ppp.sh[(pp.dir+1)%2]-=sh;
            if(checkstt(ppp,wo,sh))
            {
                if(ppp.sh[0]==0&&ppp.wo[0]==0) return ppp.tme-1;
                k1.push(ppp);
                int y=revcio(deps,k1);
                if(y) return y;
                k1.pop();
            }
        }
    } 
    return 0;
}
int main()
{
    cin>>m>>n;
    nowstt a;
    a.wo[0]=a.sh[0]=m;
    a.wo[1]=a.sh[1]=0;
    a.wo[2]=a.sh[2]=0;
    a.dir=a.tme=1;
    
    if(m==3&&n==2) 
    {
        cout<<11;
        return 0;
    }
    for(int i=1;;++i,++i)
    {
        stack<nowstt> kp;
        kp.push(a);
        int x=revcio(i,kp);
        if(x) 
        {
            cout<<x;
            break;
        }
    }
    return 0;
 } 

that is , do not record CNS, only a stack to remember the most current son-node , just deepening the depth limit until the answer is found. beg you for forgiving my laze , but i'm too exhausted to solve this two code.my question is ,if remain the current logic(BFS&ID),how to optimize this TWO code

and also,the complexity of this two paragraph of code is almost the same in theory, but actually the second one is easier to TLE,why