题解：P13710 [NWERC 2023] Klompendans

#include<bits/stdc++.h> 
using namespace std;
struct p{
    int x, y, move;
};
int main(){
    int n,a,b,c,d;
    cin>>n;
    cin>>a>>b;
    cin>>c>>d;
    vector<pair<int, int> > dirs1;// 记录第一种移动8个方向 
    dirs1.push_back(make_pair(a, b));
    dirs1.push_back(make_pair(a, -b));
    dirs1.push_back(make_pair(-a, b));
    dirs1.push_back(make_pair(-a, -b));
    dirs1.push_back(make_pair(b, a));
    dirs1.push_back(make_pair(b, -a));
    dirs1.push_back(make_pair(-b, a));
    dirs1.push_back(make_pair(-b, -a));
    vector<pair<int, int> > dirs2;// 记录第二种移动8个方向 
    dirs2.push_back(make_pair(c, d));
    dirs2.push_back(make_pair(c, -d));
    dirs2.push_back(make_pair(-c, d));
    dirs2.push_back(make_pair(-c, -d));
    dirs2.push_back(make_pair(d, c));
    dirs2.push_back(make_pair(d, -c));
    dirs2.push_back(make_pair(-d, c));
    dirs2.push_back(make_pair(-d, -c));
    vector<vector<bool> > r(n,vector<bool>(n,false));// 记录是否可达
    vector<vector<bool> > vis1(n,vector<bool>(n,false));// 记录类型1或类型2到达的位置，避免重复访问
    vector<vector<bool> > vis2(n,vector<bool>(n,false));
    r[0][0]=true;// 起点(0,0)是可达的
    queue<p> q;// BFS队列
    for (int i=0;i<dirs1.size();i++){// 如果第一步是动作1 
        int dx=dirs1[i].first;
        int dy=dirs1[i].second;
        int x=0+dx;
        int y=0+dy;
        if(x>=0&&x<n&&y>=0&&y<n&&!vis1[x][y]){
            vis1[x][y]=true;
            r[x][y]=true;
            q.push({x,y,1});
        }
    }
    // 如果第一步是动作2 
    for(int i=0;i<dirs2.size();i++){
        int dx=dirs2[i].first;
        int dy=dirs2[i].second;
        int x=0+dx;
        int y=0+dy;
        if(x>=0&&x<n&&y>=0&&y<n&&!vis2[x][y]){
            vis2[x][y]=true;
            r[x][y]=true;
            q.push({x,y,2});
        }
    }
    while(!q.empty()){// 广搜
        p c=q.front();
        q.pop();
        int nex=3-c.move;
        if(nex==1){// 动作1
            for(int i=0;i<dirs1.size();i++){
                int dx=dirs1[i].first;
                int dy=dirs1[i].second;
                int nx=c.x+dx;
                int ny=c.y+dy;
                if(nx>=0&&nx<n&&ny>=0&&ny<n&&!vis1[nx][ny]){
                    vis1[nx][ny]=true;
                    r[nx][ny]=true;
                    q.push({nx,ny,1});
                }
            }
        }
		else{// 动作2
            for(int i=0;i<dirs2.size();i++){ 
                int dx=dirs2[i].first;
                int dy=dirs2[i].second;
                int nx=c.x+dx;
                int ny=c.y+dy;
                if (nx>=0&&nx<n&&ny>=0&&ny<n&&!vis2[nx][ny]){
                    vis2[nx][ny]=true;
                    r[nx][ny]=true;
                    q.push({nx,ny,2});
                }
            }
        }
    }
    int count=0;// 统计答案 
    for(int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            if(r[i][j]){
                count++;
            }
        }
    }
    cout<<count<<endl;
    return 0;
}