3-CNF

NavalBattle

This is the 500-point question of "TopCoder" and I cannot give the full description because my Ubuntu gets frozen and everything is lost except my program.
However, I think people are familiar with this old game.
1. Two players are playing a game in one row of "fieldLength" with battleship of length of "shipLength".
2. Attacker issues its "shots" at round step which gives a vector of index of his shots.
3. Defender gives a string of "answer" which contains either "1" or "0", indicating if shot in step hits.
4. If at any step, attacker feels defender is dishonest, he must return the "step" or "round" number and stop the game.

I think my mind has been damaged for alcohol and lack of exercises. It took me a whole day. Damn it!

#include <vector>
#include <string>
#include <iostream>

using namespace std;

enum SpaceEnum
{
    Unknown = 0,
    Empty = 1,
    Ship = 2,
};

class NavalBattle
{
public:
    int firstDishonestMove(int fieldLength, int shipLength, vector<int> shots, string answers)
    {
        vector<int> fields(fieldLength, Unknown);
        for (int i = 0; i < answers.size(); i ++)
        {
            int index = shots[i];
            if (answers[i] == '0')
            {
                fields[index] = Empty;
            }
            else
            {
                fields[index] = Ship;
            }
            if (!testShots(fieldLength, shipLength, shots, answers, fields, i))
            {
                return i;
            }
        }
        return -1;
    }

    bool testAtLeastOneShip(int fieldLength, int shipLength, vector<int> shots, string answers, vector<int> fields, int step)
    {
        int i;
        for (i = 0; i <= step; i ++)
        {
            // if there is hit, at least there is one ship
            if (answers[i] == '1')
            {
                return true;
            }
        }
        // we didn't hit anything, try to see if Alice can place at least one ship
        return testShipPlacementRange(fieldLength, shipLength, fields, 0, fieldLength - shipLength);
    }

    bool testShipAdjacent(int fieldLength, int shipLength, vector<int> fields, int start)
    {
        if (start - 1 >= 0)
        {
            if (fields[start - 1] == Ship)
            {
                return false;
            }
        }
        if (start + shipLength < fieldLength)
        {
            if (fields[start + shipLength] == Ship)
            {
                return false;
            }
        }
        return true;
    }

    bool testShipPlacement(int fieldLength, int shipLength, vector<int> fields, int start)
    {
        if (!testShipAdjacent(fieldLength, shipLength, fields, start))
        {
            return false;
        }

        for (int j = 0; j < shipLength; j ++)
        {
            if (start + j < fieldLength)
            {
                if (fields[start + j] == Empty)
                {
                    return false;
                }
            }
        }
        return true;
    }

    bool testShipPlacementRange(int fieldLength, int shipLength, vector<int> fields, int start, int end)
    {
        for (int i = start; i <= end; i ++)
        {
            if (testShipPlacement(fieldLength, shipLength, fields, i))
            {
                return true;
            }
        }
        return false;
    }

    bool testHit(vector<int> shots, string answers, vector<int> fields, int step)
    {
        if (answers[step] == '0')
        {
            return fields[shots[step]] != Ship;
        }
        else
        {
            // '1'
            return fields[shots[step]] != Empty;
        }
    }

    bool testRecursivePreviousShipPlacement(int fieldLength, int shipLength, vector<int> shots, string answers, vector<int> fields, int currentStep, int endStep)
    {
        if (currentStep > endStep)
        {
            return true;
        }
        if (answers[currentStep] == '0')
        {
            return testRecursivePreviousShipPlacement(fieldLength, shipLength, shots, answers, fields, currentStep + 1, endStep);
        }
        else
        {
            int start = shots[currentStep] - shipLength + 1, end = shots[currentStep];
            if (start < 0)
            {
                start = 0;
            }
            for (int i = start; i <= end; i ++)
            {
                if (testShipPlacement(fieldLength, shipLength, fields, i))
                {
                    vector<int> nextFields(fields);
                    for (int j = 0; j < shipLength; j ++)
                    {
                        nextFields[j + i] = Ship;
                    }
                    if (testRecursivePreviousShipPlacement(fieldLength, shipLength, shots, answers, nextFields, currentStep + 1, endStep))
                    {
                        return true;
                    }
                }
            }
        }
    }
    bool testShots(int fieldLength, int shipLength, vector<int> shots, string answers, vector<int> fields, int step)
    {
        if (!testAtLeastOneShip(fieldLength, shipLength, shots, answers, fields, step))
        {
            return false;
        }

        if (!testHit(shots, answers, fields, step))
        {
            return false;
        }

        if (answers[step] == '1')
        {
            int start = shots[step] - shipLength + 1, end = shots[step];
            if (start < 0)
            {
                start = 0;
            }
            if (!testShipPlacementRange(fieldLength, shipLength, fields, start, end))
            {
                return false;
            }
            vector<int> testFields(fields.size());
            if (!testRecursivePreviousShipPlacement(fieldLength, shipLength, shots, answers, testFields, 0, step))
            {
                return false;
            }
        }
        return true;
    }
};

void test0()
{
    NavalBattle naval;
    string answer = "1";
    vector<int> shots;

    shots.push_back(0);

    cout << naval.firstDishonestMove(1, 1, shots, answer) << endl;
}

void test1()
{
    NavalBattle naval;
    string answer = "110";
    vector<int> shots;

    shots.push_back(0);
    shots.push_back(2);
    shots.push_back(1);

    cout << naval.firstDishonestMove(3, 2, shots, answer) << endl;
}

void test2()
{
    NavalBattle naval;
    string answer = "11110";
    vector<int> shots;

    shots.push_back(0);
    shots.push_back(4);
    shots.push_back(1);
    shots.push_back(3);
    shots.push_back(2);

    cout << naval.firstDishonestMove(5, 2, shots, answer) << endl;
}

void test3()
{
    NavalBattle naval;
    string answer = "0110";
    vector<int> shots;

    shots.push_back(4);
    shots.push_back(7);
    shots.push_back(8);
    shots.push_back(2);

    cout << naval.firstDishonestMove(10, 1, shots, answer) << endl;
}

void test4()
{
    NavalBattle naval;
    string answer = "01";
    vector<int> shots;

    shots.push_back(4);
    shots.push_back(2);

    cout << naval.firstDishonestMove(10, 10, shots, answer) << endl;
}

int main()
{
    test0();
    test1();
    test2();
    test3();
    test4();
    return 0;
}