SW expert academy 1227 미로2

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <utility>
#include <set>
#include <queue>
#include <stack>
#include <functional>
#include <math.h>
#include <string>

using namespace std;

int len, start;

int moves[4][2] = { {-1,0}, {0, -1}, {1, 0}, {0, 1} };
int arr[100][100];

set<pair<int, int>> adj[100][100];

int main() {

	for (int tc = 1; tc <= 10; tc++) {
		int testcasenum;

		cin >> testcasenum;

		int starti, startj, endi, endj;

		for (int i = 0; i < 100; i++) {
			string tempstr;
			cin >> tempstr;
			for (int j = 0; j < 100; j++) {
				arr[i][j] = tempstr[j] - '0';
				if (arr[i][j] == 2) {
					starti = i;
					startj = j;
				}
				else if (arr[i][j] == 3) {
					endi = i;
					endj = j;
				}
			}
		}

		for (int i = 0; i < 100; i++) {
			for (int j = 0; j < 100; j++) {
				adj[i][j].clear();
				if (arr[i][j] == 0 || arr[i][j] == 2 || arr[i][j] == 3) {
					for (int k = 0; k < 4; k++) {
						int nexti = i + moves[k][0];
						int nextj = j + moves[k][1];

						if (nexti < 0 || nexti >= 100 || nextj < 0 || nextj >= 100) {
							continue;
						}
						int next = arr[nexti][nextj];
						if (next == 0 || next == 3) {
							adj[i][j].insert(make_pair(nexti, nextj));
						}
					}
				}
			}
		}

		queue<pair<int, int>> q;
		bool isVisit[100][100];

		for (int i = 0; i < 100; i++) {
			for (int j = 0; j < 100; j++) {
				isVisit[i][j] = false;
			}
		}

		q.push(make_pair(starti, startj));
		q.push(make_pair(-1, -1));

		bool canGo = false;

		while (true) {
			auto next = q.front();
			q.pop();

			if (next.first == endi && next.second == endj) {
				canGo = true;
				break;
			}

			if (next.first != -1 && isVisit[next.first][next.second]) {
				continue;
			}

			if (q.empty()) {
				break;
			}

			if (next.first == -1) {
				q.push(make_pair(-1, -1));
			}
			else {
				isVisit[next.first][next.second] = true;
				for (auto nextnext : adj[next.first][next.second]) {
					q.push(make_pair(nextnext.first, nextnext.second));
				}
			}
		}

		printf("#%d %d\n", tc, (canGo ? 1 : 0));
	}

	return 0;
}