【題解】Luogu [04]P1747 好奇怪的遊戲[普及_提高-][BFS從入門到省選]

講道理這題就是個模板題,與馬的遍歷沒有太大區別。

注意常量數組,這回馬可以跳12個方向,自己推一下就好了

其實寫一個bfs用兩次就好了,但我當時懶得改了

const int L = 66 + 6;

int d[L][L];
bool hash[L][L];

int d1[L][L];
bool hash1[L][L];

const int dx[] = {1,2,2,1,-1,-2,-2,-1,2,2,-2,-2};
const int dy[] = {2,1,-1,-2,-2,-1,1,2,2,-2,-2,2};

class Point{
    public:int x,y;

    Point(int y,int x){
        this -> x = x;
        this -> y = y;
    }
};

void bfs(int sx,int sy){
    memset(d,0,sizeof(d));
    memset(hash,0,sizeof(hash));

    std::queue<Point> Q;

    hash[sy][sx] = false;
    d[sy][sx] = 0;
    Q.push(Point(sy,sx));

    while(Q.size()){
        int x = Q.front().x;
        int y = Q.front().y;
        Q.pop();

        for(int i = 0;i < 12;i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(!hash[ny][nx] && nx > 0 && ny > 0 && nx < L && ny < L){
                d[ny][nx] = d[y][x] + 1;
                Q.push(Point(ny,nx));
            }
            hash[ny][nx] = true;
        }
    }
}

void bfs1(int sx,int sy){
    memset(d1,0,sizeof(d1));
    memset(hash1,0,sizeof(hash1));

    std::queue<Point> Q;

    hash1[sy][sx] = false;
    d1[sy][sx] = 0;
    Q.push(Point(sy,sx));

    while(Q.size()){
        int x = Q.front().x;
        int y = Q.front().y;
        Q.pop();

        for(int i = 0;i < 12;i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(!hash1[ny][nx] && nx > 0 && ny > 0 && nx < L && ny < L){
                d1[ny][nx] = d1[y][x] + 1;
                Q.push(Point(ny,nx));
            }
            hash1[ny][nx] = true;
        }
    }
}

int main(){
    int x1,y1;
    scanf("%d %d",&x1,&y1);
    bfs(x1,y1);
    printf("%d\n",d[1][1]); 

    int x2,y2;
    scanf("%d %d",&x2,&y2);
    bfs1(x2,y2);
    printf("%d",d1[1][1]);

    return 0;
}

发布者:Cinema

成功的道路并不狭窄,因为大部分人都在颓废。

留下评论

电子邮件地址不会被公开。 必填项已用*标注