// 演算法 / Algorithm:
// 用 BFS 從 start 開始一層一層擴張，每個索引最多訪問一次。
// 走過的位置把 arr[i] 取負當作「已訪問」標記（原值非負，所以負號獨一無二）。
// BFS expands layer by layer from start; each index is visited at most once.
// We mark visited indices by negating arr[i] (values are non-negative, so negative = visited).

#include <stdbool.h>   // 引入 bool 型別 / brings in the bool type
#include <stdlib.h>    // 引入 malloc / free / abs / for malloc, free, abs

bool canReach(int* arr, int arrSize, int start) {
    // 邊界檢查：起點本身就是 0 直接回傳 true / Edge case: start is already 0.
    if (arr[start] == 0) return true;

    // 用一個整數陣列當 queue；最壞情況每個索引都進隊一次，所以大小 arrSize 就夠。
    // Use an int array as a queue; worst case each index enters once, so arrSize suffices.
    int* queue = (int*)malloc(sizeof(int) * arrSize);
    int head = 0, tail = 0;            // head 是讀取位置，tail 是寫入位置 / read & write indices

    queue[tail++] = start;             // 把起點放進 queue / enqueue the start index
    arr[start] = -arr[start];          // 立即標記已訪問（取負）/ mark visited by negating

    // 主迴圈：當 queue 還有東西就繼續 / Main loop: while the queue isn't empty.
    while (head < tail) {
        int i = queue[head++];         // 取出隊首索引 / pop the front index
        int step = -arr[i];            // 取出原始跳躍距離（之前取了負，再取負還原）/ recover original jump distance
                                       // 注意：因為已經訪問過，arr[i] 一定是負的 / arr[i] is negative here

        // 嘗試往右跳 / Try jumping right.
        int right = i + step;
        if (right < arrSize) {         // 不能跳出右邊界 / must stay in bounds
            if (arr[right] == 0) {     // 找到 0 ⇒ 成功 / found a zero ⇒ success
                free(queue);
                return true;
            }
            if (arr[right] > 0) {      // 還沒訪問過（值仍為正）/ not visited yet (still positive)
                arr[right] = -arr[right];   // 標記已訪問 / mark visited
                queue[tail++] = right;       // 入隊 / enqueue
            }
        }

        // 嘗試往左跳 / Try jumping left.
        int left = i - step;
        if (left >= 0) {               // 不能跳出左邊界 / must stay in bounds
            if (arr[left] == 0) {      // 找到 0 ⇒ 成功 / found a zero ⇒ success
                free(queue);
                return true;
            }
            if (arr[left] > 0) {       // 還沒訪問過 / not visited yet
                arr[left] = -arr[left];     // 標記 / mark
                queue[tail++] = left;        // 入隊 / enqueue
            }
        }
    }

    free(queue);                       // 記得釋放動態記憶體 / always free what you malloc
    return false;                      // queue 清空仍沒找到 0 / drained without finding 0
}