swea 1226. [S/W 문제해결 기본] 7일차 - 미로1

[문제]

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14vXUqAGMCFAYD&categoryId=AV14vXUqAGMCFAYD&categoryType=CODE

SW Expert Academy

[풀이]

bfs

 

#include <iostream>
#include <queue>
#include <cstring>//memset
#include <cstdio>//scanf
using namespace std;

struct Pos {
	int x, y;
};

int Map[16][16];
bool visited[16][16];
const int dx[] = { -1,1,0,0 };
const int dy[] = { 0,0,-1,1 };

int bfs(int startx, int starty) {
	queue<Pos>q;
	q.push({ startx,starty });
	visited[startx][starty] = true;
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		q.pop();
		if (Map[x][y] == 3)
			return 1;
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (Map[nx][ny] != 1 && visited[nx][ny] == false) {
				visited[nx][ny] = true;
				q.push({ nx,ny });
			}
		}
	}
	return 0;
}

void solution() {
	int tnum;
	int startX, startY;
	for (int t = 1; t <= 10; t++) {
		cin >> tnum;
		memset(visited, false, sizeof(visited));
		for (int i = 0; i < 16; i++) {
			for (int j = 0; j < 16; j++) {
				scanf("%1d", &Map[i][j]);
				if (Map[i][j] == 2) {
					startX = i;
					startY = j;
				}
			}
		}
		cout << '#' << tnum << ' ' << bfs(startX, startY) << '\n';
	}
}

int main() {
	solution();
	return 0;
}