[PS][완전탐색][BFS]/[BOJ][2178][미로 탐색]

boj2178.cpp

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n=0, m=0;
int map[100][100];
int dist[100][100];
bool visited[100][100];
queue<pair<int, int> > q;
int dx[4] ={0,0,1,-1};
int dy[4] ={1,-1,0,0};
void bfs(int x, int y){
	dist[x][y]= 1;
	visited[x][y] = true;
	q.push(make_pair(x,y));
	while(!q.empty()){
		pair<int, int> curr = q.front();
		q.pop();
		for(int k=0; k<4; k++){
			int nx = curr.first + dx[k];
			int ny = curr.second + dy[k];
			if(nx<0 || nx>=n) continue;
			if(ny<0 || ny>=m) continue;
			if(!map[nx][ny]) continue;
			if(visited[nx][ny]) continue;
			q.push(make_pair(nx,ny));
			dist[nx][ny] = dist[curr.first][curr.second] + 1;
			visited[nx][ny] = true;
		}
	}
}

int main (void){
	cin>> n>> m;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			scanf("%1d", &map[i][j]);
		}
	}

	bfs(0,0);
	// for(int i=0; i<n; i++){
	// 	for(int j=0; j<m; j++){
	// 		cout<< dist[i][j]<<" ";
	// 	}
	// 	cout<<"\n";
	// }
	cout<<dist[n-1][m-1];
	return 0;
}