4방향 탈출이 가능한지 확인

n * m 2차원 영역의 왼쪽 위 모서리에서 뱀에게 물리지 않고 오른쪽 아래 모서리로 탈출하려고 합니다. 이동 시 인접한 사각형으로는 상하좌우로만 이동할 수 있으며, 뱀이 있는 사각형으로는 이동할 수 없습니다. 예를 들어 다음과 같은 뱀의 경우 실선과 같은 경로로 탈출할 수 있습니다. 이 시점에서 뱀에게 물리지 않고 탈출 경로가 있는지 판단하는 코드를 작성합니다.

입력 형식

첫 번째 줄에서 n과 m 사이에 공백을 두고 지정합니다.

2번째 줄부터 (n+1)번째 줄까지는 각 줄에 Queue가 없으면 1, Queue가 있으면 0을 공백을 두고 입력한다. 시작 및 끝 필드에 뱀이 표시되지 않는다고 가정할 수 있습니다.

• 2≤n, m≤100

출력 형식

뱀에게 물리지 않고 왼쪽 위 모서리에서 오른쪽 아래 모서리까지 탈출할 수 있는 경로가 있으면 1을 반환하고 그렇지 않으면 0을 반환합니다.

---

내 솔루션

#include <iostream>
#include <queue>
using namespace std;
#define MAX_N 100
#define MAX_M 100

int n, m;
int a(MAX_N)(MAX_M);

// bfs에 필요한 변수들 입니다.
queue<pair<int, int> > q;
bool visited(MAX_N)(MAX_M);

bool InRange(int x, int y) { // 격자 안인지
    return 0 <= x && x < n && 0 <= y && y < m;
}

bool CanGo(int x, int y) { // 격자 안, 뱀이 없음, 방문한적 없음
    return InRange(x, y) && a(x)(y) && !visited(x)(y);
}

bool bfs(int x, int y){
    int dx(4) = {1,0,0,-1};
    int dy(4) = {0,1,-1,0}; // 격자이므로
    q.push(make_pair(x,y));
    visited(x)(y)=1;

    while(!q.empty()){
        pair<int,int> a = q.front();
        q.pop();
        for(int i=0; i<4; ++i){
            int new_x = a.first + dx(i);
            int new_y = a.second + dy(i);
            if(CanGo(new_x, new_y)){
                visited(new_x)(new_y) = 1;
                q.push(make_pair(new_x, new_y));
            }
        }
    }
    cout << visited(n-1)(m-1);
}

int main() {
    cin>>n>>m;
    for(int i=0; i<n; ++i){
        for(int j=0; j<m; ++j){
            cin>>a(i)(j);
        }
    }
    bfs(0,0);
    return 0;
}

탐색이 어렵다…

이것은 격자 문제이기 때문에 네 방향으로 가야 하는데,

쌍을 만들고 누르십시오