ZeroJudge D105: Passing Balls

During PE class, Xiaoman's teacher often organizes games with the students. This time, the teacher has the students play a ball-passing game. The rules of the game are as follows: N students stand in a circle, and one student holds a ball. When the teacher blows the whistle, the passing begins. Each student can pass the ball to either of the two students next to them (left or right). When the teacher blows the whistle again, the passing stops and the student who is holding the ball at that moment is the loser and has to perform for everyone.
Xiaoman posed an interesting question: How many different ways are there to pass the ball starting from Xiaoman, such that after M passes, the ball is back with Xiaoman? Two passing methods are considered different if and only if the sequence of students who receive the ball is different. For example, if there are three students, numbered 1, 2, and 3, and Xiaoman is number 1, the ball can be passed 3 times and return to Xiaoman in 2 different ways: 1 -> 2 -> 3 -> 1 and 1 -> 3 -> 2 -> 1.

Sample Inputs/Outputs

Thought Process

Use BFS to handle the problem. Each time, calculate to whom the ball should be passed and sum up the counts for each starting point. You can use a map for storage, and every time you run BFS, return this map. When the number of BFS steps equals M, output the value in the map for the first person.

Sample Code－ZeroJudge D105: Passing Balls

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int N, M;

void BFS(vector<int>start, int count, map<int, int>MAP)
{
    vector<int>newStart;
    map<int, int>exist;
    for (int i = 0; i<start.size(); i++)
    {
        int left = start[i] - 1, right = start[i] + 1;
        if (left < 1) left = N;
        if (right > N) right = 1;
        if (exist[left] == 0) newStart.push_back(left);
        if (exist[right] == 0) newStart.push_back(right);
        exist[left] += MAP[start[i]];
        exist[right] += MAP[start[i]];
    }
    if (count == M-1)
    {
        cout << exist[1] << "\n";
        return;
    }
    BFS(newStart, count+1, exist);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    cout.sync_with_stdio(0);
    cout.tie(0);
    cin >> N >> M;
    if (M == 1) cout << "0\n";
    else
    {
        vector<int>start;
        start.push_back(1);
        map<int, int>MAP;
        MAP[1] = 1;
        BFS(start, 0, MAP);
    }
}

//ZeroJudge D105
//Dr. SeanXD