백준 1400번 _ 화물차

www.acmicpc.net/problem/1400

1400번: 화물차

---

코드

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

using namespace std;

class TrafficLight
{
public:
	int y;
	int x;
	char startlight;
	int eastWestTime;
	int southNorthTime;
};

class BfsData
{
public:
	int y;
	int x;
	int currentTime;
	vector<vector<bool>> visit;
	BfsData(int y_in, int x_in, int currentTime_in, vector<vector<bool>> visit_in):y(y_in), x(x_in), currentTime(currentTime_in),visit(visit_in){}
};

int m, n;
char map[20][20];
int numOfTrafficLight = -1;
TrafficLight trafficLights[10];
pair<int, int> startPoint;
pair<int, int>endPoint;
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };



bool IsInRange(int y, int x)
{
	if (y >= 0 && y < m && x >= 0 && x < n)
		return true;
	return false;
}

void print(int y, int x)
{
	cout << y << ' ' << x << endl;
}

void printVisit(vector<vector<bool>>& visit)
{
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cout << visit[i][j] << ' ';
		}
		cout << endl;
	}
}

//dir 0 1은 남북 2 3은 동서임
bool IsPossibleToGo(int IdxOfTrafficLight, int currentTime, int dir)
{
	TrafficLight trafficLight = trafficLights[IdxOfTrafficLight];
	char startLight = trafficLight.startlight;
	int eastWestTime = trafficLight.eastWestTime;
	int southNorthTime = trafficLight.southNorthTime;
	char currentLight;

	if (startLight == '-')
	{
		int aTime = 0;
		while (1)
		{
			aTime += eastWestTime;
			if (aTime >= currentTime)
			{
				currentLight = '-';
				break;
			}
			aTime += southNorthTime;
			if (aTime >= currentTime)
			{
				currentLight = '|';
				break;
			}
		}
	}
	else if (startLight == '|')
	{
		int aTime = 0;
		while (1)
		{
			aTime += southNorthTime;
			if (aTime >= currentTime)
			{
				currentLight = '|';
				break;
			}
			aTime += eastWestTime;
			if (aTime >= currentTime)
			{
				currentLight = '-';
				break;
			}
		}
	}
	if (currentLight == '-')
	{
		if (dir == 2 || dir == 3)
			return true;
		return false;
	}
	else
	{
		if (dir == 0 || dir == 1)
			return true;
		return false;
	}
}

void simulation()
{
	int answer = 0;

	vector<vector<bool>>visitInit;
	visitInit.resize(m);
	for (int i = 0; i < m; i++)
		visitInit[i].resize(n);

	BfsData bfsData(startPoint.first, startPoint.second, 0, visitInit);
	queue<BfsData> que;
	que.push(bfsData);

	while (!que.empty())
	{
		int y = que.front().y;
		int x = que.front().x;
		int currentTime = que.front().currentTime;
		vector <vector<bool>>visit = que.front().visit;
		que.pop();

		//여기서 할 처리들 , visit 같은거
		visit[y][x] = true;
		
		/*printVisit(visit);
		cout << "currentTime : " << currentTime << endl;*/

		//도착했는지 확인
		if (y == endPoint.first && x == endPoint.second)
		{
			answer = currentTime;
			break;
		}

		//네방향을 살펴보고 que에 넣는다.
		for (int i = 0; i < 4; i++)
		{
			int ny = y + dy[i];
			int nx = x + dx[i];

			//범위넘으면
			if (IsInRange(ny, nx) == false)
				continue;

			//길이 아니라면
			if (map[ny][nx] == '.')
				continue;

			//이미 왔던 길이라면
			if (visit[ny][nx] == true)
				continue;

			//교차로일시 갈수 있는지 없는지 확인
			if (isdigit(map[ny][nx]) != 0)
			{
				int IdxOfTraffic = map[ny][nx] - '0';
				//갈수 있다면
				if(IsPossibleToGo(IdxOfTraffic, currentTime+1, i) == true)
				{
					BfsData temp(ny, nx, currentTime + 1, visit);
					que.push(temp);
					continue;
				}
				//갈수 없다면
				else
				{
					BfsData temp(y, x, currentTime + 1, visit);
					que.push(temp);
					continue;
				}
			}
			//이때는 길이나 도착지점임
			else
			{
				BfsData temp(ny, nx, currentTime + 1, visit);
				que.push(temp);
			}
		}
	}

	if (answer == 0)
		cout << "impossible" << '\n';
	else
		cout << answer << '\n';
}

void InputAndSolve()
{
	//map
	cin >> m >> n;

	if (m == 0 && n == 0)
		return;

	numOfTrafficLight = -1;
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			char mapData;
			cin >> mapData;
			map[i][j] = mapData;

			if (mapData == 'A')
				startPoint = { i, j };
			else if (mapData == 'B')
				endPoint = { i, j };
			else if (isdigit(mapData) != 0)
			{
				numOfTrafficLight = max(numOfTrafficLight, mapData - '0');
				trafficLights[mapData - '0'].y = i;
				trafficLights[mapData - '0'].x = j;
			}
		}
	}

	//교차로 데이터값
	for (int i = 0; i <= numOfTrafficLight; i++)
	{
		int num, eastWestTime, southNorthTime;
		char startlight;

		cin >> num >> startlight >> eastWestTime >> southNorthTime;
		trafficLights[num].startlight = startlight;
		trafficLights[num].eastWestTime = eastWestTime;
		trafficLights[num].southNorthTime = southNorthTime;
	}

	simulation();
}

int main()
{
	while (1)
	{
		InputAndSolve();
		if (m == 0 && n == 0)
			break;
	}
	return 0;
}