Algoogle

Algorithm for Programming Contest

POI III Rooks

Category: POI Tag: greedy

Rooks

問題概要


n*nのチェス盤にルークをn個置く.
ただし各ルークは他のルークから取れる位置に置かれない(Nクイーン問題の簡易版).
今各ルークを置く位置の範囲を矩形で与えられる.
それを満たすような置き方があるならそれを求めよ.
存在しないならNIEと出せ

解法


横と縦を分けて考えることができる.
なぜならどの行, 列にもただひとつルークが存在するような置き方をし, 縦と横だけで区間が決まっているため.
よって以下の操作を縦と横でやって合わせればよい.

位置iについて, そこから始まる区間の終端とidの組を候補リストに加える.
もし位置iより右端が大きい候補が存在しなければ位置iに対応するルークが存在しないのでNIE
存在するならそのうち右端が一番小さいルークを置く.

コード


(rooks.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

vector<pii> ac[1<<12], bd[1<<12];
int n, x[1<<12], y[1<<12];

bool calc(vector<pii> lr[], int w[])
{
        priority_queue<pii, vector<pii>, greater<pii> >  q;
        for (int i = 0; i < n; i++) {
                for (int j = 0; j < (int)lr[i].size(); j++) q.push(lr[i][j]);
                if(q.empty()) return 0;
                pii p = q.top(); q.pop();
                if(p.first <= i) return 0;
                w[p.second] = i;
        }
        return 1;
}

void solve()
{
        if(!calc(ac,x) or !calc(bd,y)) puts("NIE");
        else {
                for (int i = 0; i < n; i++)
                        printf("%d %d\n", x[i]+1, y[i]+1);
        }
        return;
}

void input()
{
      scanf("%d", &n);
      int a, b, c, d;
      for (int i = 0; i < n; i++) {
              scanf("%d%d%d%d", &a, &b, &c, &d);
              ac[a-1].push_back(pii(c,i));
              bd[b-1].push_back(pii(d,i));
      }

}

int main()
{
        input();
        solve();
        return 0;
}

Comments