백준 침투

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

13565번: 침투

bfs 가볍게 풀기

#include <iostream>
#include <vector>
#include <queue>
#include<string>
#include<algorithm>
#include<cmath>
#include<unordered_map>
#include<map>
#include<stack>
using namespace std;

struct Point {
	int i, j, t, cnt, power;
	char c;
};

void Prints(vector<vector<int>>maps, int n, int m) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << maps[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}

void Prints(vector<vector<bool>>maps, int n, int m) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << maps[i][j];
		}
		cout << endl;
	}
	cout << endl;
}
void Prints(vector<vector<char>>maps, int n, int m) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << maps[i][j];
		}
		cout << endl;
	}
	cout << endl;
}
void Prints(vector<vector<vector<char>>>maps, int n, int m, int k) {
	for (int t = 0; t < k; t++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				cout << maps[t][i][j];
			}
			cout << endl;
		}
		cout << endl;
	}
	cout << endl;
}

void Prints(vector<vector<vector<bool>>>maps, int n, int m, int k) {
	for (int t = 0; t < k; t++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				cout << maps[t][i][j];
			}
			cout << endl;
		}
		cout << endl;
	}
	cout << endl;
}
void Prints(string str, int n) {
	for (int i = 0; i < n; i++) {
		cout << str[i] << ",";
	}
	cout << endl;
}

struct Data {
	unsigned long long index;
	unsigned long long value;
};

bool compares(const Point &a, const Point &b) {
//	if (a.s == b.s) {
	//	return a.e > b.e;
	//}
	//return a.s > b.s;
	return false;
}


int main() {
	int m, n;
	cin >> m >> n;
	vector<vector<int>>maps;
	vector<bool>tmpbVisited(n,false);
	vector<vector<bool>>bVisited(m, tmpbVisited);
	for (int i = 0; i < m; i++) {
		string str;
		cin >> str;
		vector<int>tmpMaps;
		for (int j = 0; j < n; j++) {
			int tmp = str[j] - '0';
			tmpMaps.push_back(tmp);
			if (tmp == 1) {
				bVisited[i][j] = true;
			}
		}
		maps.push_back(tmpMaps);
	}
	//Prints(maps, m, n);
	vector<Point>starts;

	for (int j = 0; j <n; j++) {
		if (maps[0][j] == 0) {
			Point tmpP;
			tmpP.i = 0;
			tmpP.j = j;
			starts.push_back(tmpP);
		}
	}
	bool bEnd = false;
	for (int i = 0; i < starts.size(); i++) {
		Point p;
		p.i = starts[i].i;
		p.j = starts[i].j;
		queue<Point>q;
		q.push(p);
		int diri[] = { 1,-1,0,0 };
		int dirj[] = { 0,0,1,-1 };
		while (!q.empty()) {
			
			
			Point start = q.front();
			q.pop();
			if (start.i == m - 1) {
				bEnd = true;
			}
			if (bEnd == true) {
				break;
			}
			for (int k = 0; k < 4; k++) {
				int tmpDiri = start.i + diri[k];
				int tmpDirj = start.j + dirj[k];
				if (tmpDiri == -1 || tmpDirj == -1 || tmpDiri >= m || tmpDirj >= n) {
					continue;
				}

				if (bVisited[tmpDiri][tmpDirj] == true) {
					continue;
				}
				if (tmpDiri == m - 1) {
					bEnd = true;
				}
				bVisited[tmpDiri][tmpDirj] = true;
				Point tmpP;
				tmpP.i = tmpDiri;
				tmpP.j = tmpDirj;
				//Prints(bVisited, m, n);
				q.push(tmpP);

			}
		}
	}
	if (bEnd == false) {
		cout << "NO";
	}
	else {
		cout << "YES";
	}
	
	
	
	return 0;
}