백준 2178번 C++

#include <iostream>

#include <queue>

#include <string>

using namespace std;

const int MAX=101;

int n, m;

int arr[MAX][MAX];

queue<pair<int, pair<int,int>>> way;

int visited[MAX][MAX];

typedef struct {

int x, y;

}Move;

Move mv[4] = { {0,-1},{0,1},{1,0},{-1,0} };

int bfs() {

int answer = 0;

way.push(make_pair(1,make_pair(1,1)));

visited[1][1] = 1;

while (!way.empty()) {

int x = way.front().first;

int y = way.front().second.first;

int count = way.front().second.second;

if ((x == n) && (y == m)) {

answer = count;

break;

}

way.pop();

for (int i = 0; i < 4; i++) {

int mx = x + mv[i].x;

int my = y + mv[i].y;

if (mx >= 1 && mx <= n && my >= 1 && my <= m) {

if ((arr[mx][my] == 1) && (visited[mx][my] == -1)) {

visited[mx][my] = 1;

way.push(make_pair(mx, make_pair(my, count+1)));

}

}

}

}

return answer;

}

int main(void) {

cin >> n >> m;

for (int i = 1; i <= n; i++) {

string number;

cin >> number;

for (int j = 1; j <= m; j++) {

arr[i][j] = number[j-1] - '0';

}

}

memset(visited, -1,sizeof(visited));

cout << bfs();

return 0;

}