목록유니온 파인드 (1)
블로그 옮겼습니다
Codeforces Round #420 (Div. 2) D. Okabe and City
http://codeforces.com/contest/821/problem/D \(n,m,k\le{10^4}\)세로 n, 가로 m 인 n * m 크기의 격자판의 (1,1) 에서 (n,m) 까지 이동하고싶다.격자판의 k개의 칸에는 불이 켜져있다. (1,1)은 무조건 켜져있다. 이동할 때에는 무조건 불이 켜져있는 칸만 밟을 수가 있다.하지만 코인 1개를 사용하면 한 행 전체, 혹은 한 열 전체의 불을 켤 수가 있다.한번에 하나의 열 또는 행만 켤 수가 있으며 만약 불을 켜는 행이나 열을 바꾸고 싶다면원래 부터 불이 켜져있던 칸으로 이동을 해야 한다. 물론 바꾸면 이전에 켠 행(열)은 원래 켜져있던 칸을 빼고는 다 꺼지고 새로운 행(열)이 켜지며 또 코인 1개가 든다.이 때 (1,1) 부터 (n,m) 까지가는..
Algorithm/Problem Solving
2017. 6. 26. 10:54