Entscheidungsproblem

#include <bits/stdc++.h>

using namespace std;

int n, s, c;
int valueSet;
vector<vector<int> > stateTable;
vector<vector<int> > moveTable;
vector<vector<int> > memo;
vector<int> tape;
vector<bool> sol;

bool rec(int pos, int state){
    //cout<<"*rec* pos: "<<pos<<" state: "<<state<<"\n";
    if(pos == 0)
        return true;
    //cout<<"first passed\n";

    int &ref = memo[pos][state];
    //cout<<"ref: "<<ref<<endl;
    if(ref == valueSet)
        return false;
    if(ref != -1 && sol[ref])
        return true;
    ref = valueSet;
    //cout<<"second passed\n";

    //cout<<"trying: stateTable["<<tape[pos]<<"]["<<state<<"]";
    int sT = stateTable[state][tape[pos]];
    //cout<<"sT: "<<sT<<endl;

    //cout<<"trying: moveTable["<<tape[pos]<<"]["<<state<<"]";
    int mT = moveTable[state][tape[pos]];
    //cout<<"mT: "<<mT<<endl;

    return rec(pos+mT, sT);
}

int main(){
    ifstream in("input.txt");
    in>>n>>s>>c;

    stateTable.resize(s);
    moveTable.resize(s);
    for(int i=0; i<s; i++){
        vector<int> tempS(c);
        vector<int> tempM(c);
        for(int j=0; j<c; j++){
            int t1, t2, t3, t4;
            in>>t1>>t2>>t3>>t4;
            tempS[j] = t3;
            tempM[j] = t4;
        }
        stateTable[i] = tempS;
        moveTable[i] = tempM;
    }

    tape.resize(n);
    for(int i=0; i<n; i++)
        in>>tape[i];

    vector<int> t(s, -1);
    memo.assign(n, t);
    in.close();

    /*cout<<"s1: "<<s<<" s2: "<<stateTable.size()<<endl;
    cout<<"c1: "<<c<<" c2: "<<stateTable[0].size()<<endl;

    cout<<"state:\n";
    for(int i=0; i<s; i++){
        for(int j=0; j<c; j++){
            cout<<stateTable[i][j]<<" ";
        }
        cout<<endl;
    }

    cout<<"move:\n";
    for(int i=0; i<s; i++){
        for(int j=0; j<c; j++){
            cout<<moveTable[i][j]<<" ";
        }
        cout<<endl;
    }*/

    sol.assign(n, false);
    int cont = 0;
    for(int i=0; i<n; i++){
        valueSet = i;
        if(rec(i, 0)){
            sol[i] = true;
            cont++;
        }
    }

    ofstream out("output.txt");
    out<<cont<<endl;
    for(int i=0; i<n; i++)
        if(sol[i])
            out<<i<<endl;
    out.close();
    return 0;
}