10월 2일 20시에 있었던 SRM368 의 DIV 1 결과 입니다~ (상위10명 + 150등 이내 한국인 + Petr)

Problem-setter 는 misof 였으며, Winner 의 점수가 1000점이 안될정도로 참가자들을 안드로메다로 보내버린 SRM 이었습니다;;
오죽하면 Petr 의 등수가 저렇겠습니까 -0-

Easy (250 pts.)
* 문제설명 : 2차원의 보드가 주어지고 각 점에는 1~9 의 숫자 또는 H 라는 문자가 적혀있다. 여기서 H 는 구멍(hole)을 뜻한다. 말은 위, 아래, 왼쪽, 오른쪽 네방향으로 현재 위치해있는 점에 적혀있는 숫자만큼 이동을 할 수 있으며, 말이 구멍에 위치하거나 보드 밖으로 나가게 되면 게임이 끝나게 된다. 좌측상단에 처음 말이 놓여있다고 할때 말을 최대한 많이 이동했을 때의 횟수를 구하여라. (단, 무한히 움직일 수 있다면 -1 로 표현한다.)
* 해결방법 : BFS 로 n( > 0) 번 이동했을 때 도달할 수 있는 위치를 저장하면서 더이상 진행하지 못할 때까지 루프를 돈다. 단 n >= row * col 일때는 비둘기집의 원리에 의하여 이미 한번 방문한 곳을 다시 방문할 수 밖에 없다. 따라서 n >= row * col 일 때는 -1 을 되돌려 주면 된다.

Medium (500 pts.)
* 문제설명 : 여러개의 선분들이 연속되어 연결되있는 것을 polyline 이라고 한다. 이 polyline 이 서로 교차하는 점이 있을 경우 하나의 이미지로 인식된다. 이 때, 주어진 polyline 들로 만들어지는 이미지의 갯수를 구하여라.
* 해결방법 : polyline 들 간의 교차여부를 확인한 후에 union-find 를 통해서 그룹의 갯수를 세면 된다. 두 개의 polyline 의 교차는 각 polyline 에 속해있는 선분들 간의 교차를 확인하여 하나라도 교차하는 경우가 있으면, 두 개의 polyline 은 교차하는 것이다. 선분간의 교차는 CCW 함수와 예외 케이스 하나를 처리해주면 쉽게 해결된다.
[code c++]
int ccw(point pa, point pb, point pc) {
return (pa.x - pb.x) * (pb.y - pc.y) - (pb.x - pc.x) * (pa.y - pb.y);
}
bool InLine(line l, point p) {
if (min(l.pa.x, l.pb.x) <= p.x && p.x <= max(l.pa.x, l.pb.x) && min(l.pa.y, l.pb.y) <= p.y && p.y <= max(l.pa.y, l.pb.y))
return true;
return false;
}
bool Intersect(line la, line lb) {
int c1 = ccw(la.pa, la.pb, lb.pa), c2 = ccw(la.pa, la.pb, lb.pb);
int c3 = ccw(lb.pa, lb.pb, la.pa), c4 = ccw(lb.pa, lb.pb, la.pb);
if (c1 == 0 && c2 == 0 && c3 == 0 && c4 == 0) {
if (InLine(la, lb.pa) || InLine(la, lb.pb) || InLine(lb, la.pa) || InLine(lb, la.pb))) return true;
return false;
}
if (c1 * c2 <= 0 && c3 * c4 <= 0) return true;
return false;
}
[/code]