백준 16469번 소년 점프 C++

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

16469번: 소년 점프

 

bfs

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>

using namespace std;

int r, c;

int dRow[4] = { -1,0,1,0 };
int dCol[4] = { 0,1,0,-1 };

vector<vector<int>> board;
vector<vector<bool>> ansBoard;
vector<vector<vector<bool>>> found;

struct Info {
	int row;
	int col;
	int id;
	int moveCnt;
};

int main()
{
	cin >> r >> c;
	board = vector<vector<int>>(r, vector<int>(c));
	ansBoard = vector<vector<bool>>(r, vector<bool>(c, false));
	found = vector<vector<vector<bool>>>(r, vector<vector<bool>>(c, vector<bool>(3, false)));
	for (int i = 0; i < r; i++) {
		string str;
		cin >> str;
		for (int j = 0; j < c; j++) {
			board[i][j] = str[j] - '0';
		}
	}
	queue<Info> q;
	for (int i = 0; i < 3; i++) {
		int row, col;
		cin >> row >> col;
		q.push({ row - 1,col - 1,i,0 });
		found[row - 1][col - 1][i] = true;
	}
	int ans = 987654321;
	int cnt = 0;
	while (!q.empty()) {
		Info curr = q.front();
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nextRow = curr.row + dRow[i];
			int nextCol = curr.col + dCol[i];
			if (nextRow < 0 || nextRow >= r) continue;
			if (nextCol < 0 || nextCol >= c) continue;
			if (found[nextRow][nextCol][curr.id]) continue;
			if (board[nextRow][nextCol] == 1) continue;
			found[nextRow][nextCol][curr.id] = true;
			q.push({ nextRow,nextCol,curr.id,curr.moveCnt + 1 });

			int foundCnt = 0;
			for (int j = 0; j < 3; j++) {
				if (found[nextRow][nextCol][j]) foundCnt++;
			}

			if (foundCnt < 3) continue;

			if (ansBoard[nextRow][nextCol] == false) {
				if (ans == curr.moveCnt + 1) {
					cnt++;
				}
				if (ans > curr.moveCnt + 1) {
					ans = curr.moveCnt + 1;
					cnt = 1;
				}
				ansBoard[nextRow][nextCol] = true;
			}
		}
	}
	if (ans == 987654321) cout << -1;
	else cout << ans << "\n" << cnt;
}