eolymp
bolt
Try our new interface for solving problems
Məsələlər

King Slime

King Slime

There is a grid of size \textbf{W}×\textbf{H} surrounded by walls. Some cells in the grid are occupied by slimes. The slimes want to unite with each other and become a "King Slime". In each move, a slime can move to east, west, south and north direction until it enters a cell occupied by another slime or hit the surrounding wall. If two slimes come together, they unite and become a new slime. Your task is write a program which calculates the minimum number of moves that all the slimes unite and become a King Slime. Suppose slimes move one by one and they never move simultaneously. \InputFile The first line contains three integers \textbf{N} (\textbf{2} ≤ \textbf{N} ≤ \textbf{40000}), \textbf{W} and \textbf{H} (\textbf{1} ≤ \textbf{W}, \textbf{H} ≤ \textbf{100000}), which denote the number of slimes, the width and the height of the grid respectively. The following \textbf{N} lines describe the initial coordinates of the slimes. The \textbf{i}^th line contains two integers \textbf{x_i} (\textbf{1} ≤ \textbf{x_i} ≤ \textbf{W}) and \textbf{y_i} (\textbf{1} ≤ \textbf{y_i} ≤ \textbf{H}), which indicate the coordinates of the \textbf{i}^th slime . All the coordinates are \textbf{1}-based. You may assume that each cell is occupied by at most one slime initially. \OutputFile Output the minimum number of moves that all the slimes unite and become a King Slime.
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
4 3 3
1 1
1 3
3 1
3 3
Çıxış verilənləri #1
3
Mənbə The 2011 35th Annual ACM Programming Contest Winter Camp