//
// Created by 罗炳国 on 2023/11/12.
//

#ifndef PFJ_CODE029_LIGHTPROBLEM_H
#define PFJ_CODE029_LIGHTPROBLEM_H

#include "commonHeader.h"

/**
 * 给定一个数组arr，长度为N，arr中的值不是0就是1
 * arr[i]表示第i栈灯的状态，0代表灭灯，1代表亮灯
 * 每一栈灯都有开关，但是按下i号灯的开关，会同时改变i-1、i、i+1栈灯的状态
 * 问题一：
 * 如果N栈灯排成一条直线,请问最少按下多少次开关,能让灯都亮起来，若不能让所有灯都亮起来则返回系统最大值
 * 排成一条直线说明：
 * i为中间位置时，i号灯的开关能影响i-1、i和i+1
 * 0号灯的开关只能影响0和1位置的灯
 * N-1号灯的开关只能影响N-2和N-1位置的灯
 *
 * 问题二：
 * 如果N栈灯排成一个圈,请问最少按下多少次开关,能让灯都亮起来
 * 排成一个圈说明：
 * i为中间位置时，i号灯的开关能影响i-1、i和i+1
 * 0号灯的开关能影响N-1、0和1位置的灯
 * N-1号灯的开关能影响N-2、N-1和0位置的灯
 *
 **/

const int MAX_VALUE = INT32_MAX;

class code029_lightProblem {
public:
    // 无环灯暴力版本
    int noloopRight(vector<int> &arr) {

    }

    /**
     * 当前在nextIndex-1位置上做决定
     * 上一个位置状态preState
     * 当前位置状态
     * 返回值：从当前位置开始到后面全亮所以按下按钮数，无法实现 MAX_VALUE
     * 预设前提。当前0 - cur-2 一定是点亮的
     **/
    int process1(vector<int> &arr, int nextIndex, int preState, int curState) {
        if (nextIndex == arr.size()) //来到了最后一个位置,当前位置与上一个位置一样，0开灯，1不动
            return curState == preState ? (curState ^ 1) : MAX_VALUE;
        if (preState == 0) { // 之前状态是0，一定需要改变
            curState ^= 1;
            int cur = arr[nextIndex] ^ 1;
            int next = process1(arr, nextIndex + 1, curState, cur);
            return next == MAX_VALUE ? MAX_VALUE : (next + 1);
        } else { // 一定不能改变，前一个位置不能再改变
            return process1(arr, nextIndex + 1, curState, arr[nextIndex]);
        }

    }

    // 无环灯递归版本
    int noloopMinStep1(vector<int> &arr) {
        int N = arr.size();
        if (N == 1)
            return arr[0] == 0;
        if (N == 2)
            return arr[0] == arr[1] ? arr[0] ^ 1 : MAX_VALUE;

        // 不改变0位置的状态
        int p1 = process1(arr, 2, arr[0], arr[1]);
        // 改变0位置的状态
        int p2 = process1(arr, 2, arr[0] ^ 1, arr[1] ^ 1);
        if (p2 != MAX_VALUE)
            p2++;
        return min(p1, p2);
    }

    // 无环灯迭代版本
    int noloopMinStep2(vector<int> &arr) {

    }

    // 问题2：有环递归版本
    int loopMinStep1(vector<int> &arr) {

    }

    int process2(vector<int> &arr,
                 int nextIndex, int preState, int curState,
                 int endStatus, int startStatus) {

    }
};

#endif//PFJ_CODE029_LIGHTPROBLEM_H