[伯俊]16174号跳躍王

2266 ワード
白駿 テキストリンク

[伯俊]16174号跳躍王


質問リンク:https://www.acmicpc.net/problem/16174

質問する



にゅうしゅつりょく



質問へのアクセス


これはグラフ探索問題です.
bfsを用いて問題を解決した.
各位置の数字に基づいて、右と下のパスをチェックし、できれば対応するノードを追加します.(N−1,N−1)ノードに到達した場合、true、到達しなかった場合falseが出力される.

コード実装（C++）

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

int N;
int map[64][64];
int check[64][64];
int moveX[2] = {0,1};
int moveY[2] = {1,0};

bool bfs(){
    queue<pair<int,int> > q;
    check[0][0] = true;

    q.push(make_pair(0,0));

    while(!q.empty()){
        int x = q.front().first; int y = q.front().second;
        q.pop();
        if(map[y][x] == -1) return true;
        for(int i = 0 ; i < 2 ; i++){
            int nextX = x + moveX[i]*map[y][x]; int nextY = y + moveY[i]*map[y][x];
            if(nextX >= N || nextY >= N || check[nextY][nextX]) continue;
            check[nextY][nextX] = true;
            q.push(make_pair(nextX,nextY));
            
        }
    }
    return false;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;

    for(int i = 0 ; i < N ; i++){
        for(int j = 0 ; j < N ; j++){
            cin >> map[i][j];
        }
    }

    memset(check, false, sizeof(check));
    if(bfs()) cout << "HaruHaru\n";
    else cout << "Hing\n";
}
[CS] React Router Day-20
[Webデザイン]チェックボックススタイル