[BOJ] 13565 침투

문제: https://www.acmicpc.net/problem/13565

 

 

문제 풀이:

맨 윗줄에서 0인 위치를 큐에 넣어놓고 시작해서 

마지막 줄에 도달하는지만 보면 된다.

 

 

소스 코드:

#include <iostream>
#include <vector>
#include <string.h>
#include <queue>
#include <string>
using namespace std;

typedef pair<int, int> P;
int n, m;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1, -1, 0, 0 };
char arr[1002][1002];
bool visit[1002][1002];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	queue<P> q;
	for (int i = 0; i < m; i++) {
		if (arr[0][i] == '0') q.push({ 0,i });
	}
	while (!q.empty()) {
		int curx = q.front().first;
		int cury = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int xx = curx + dx[i];
			int yy = cury + dy[i];
			if (xx<0 || xx>=n || yy<0 || yy>=m || visit[xx][yy]||arr[xx][yy]=='1') continue;
			if (xx == n - 1) {
				cout << "YES\n";
				return 0;
			}
			visit[xx][yy] = true;
			q.push({ xx,yy });
		}
	}
	cout<<"NO\n";
	return 0;
}