Cerinta completa
Nina has an chessboard and jumping rooks. Every cell of the chessboard is either blocked or free, and Nina can only put a single rook in any free cell.
Two jumping rooks beat each other if they are either in the same row or in the same column and all cells between them are free (note that it’s possible that there are some other rooks between them). More formally, if the first rook is in cell and the second rook is in cell (where ), then these two rooks beat each other if and only if are free. If the rooks are in cells and , then cells must all be free.
Given the configuration of the chessboard and some , help Nina place jumping rooks in the chessboard’s free cells such that the number of pairs of rooks that beat each other is minimal. Then print a single integer denoting the number of rooks that beat each other.
Input Format
The first line contains two space-separated integers describing the respective values of (the size of the chessboard) and (the number of rooks to place).
Each line of the subsequent lines contains a string of characters describing each row in the chessboard. The character of the line is # if cell is blocked or . if the cell is free.
Constraints
- It is guaranteed that is less than the number of free cells in the chessboard.
Output Format
Print a single integer denoting the minimum possible number of pairs of rooks that beat each other.
Sample Input 0
3 4
...
...
...
Sample Output 0
2
Explanation 0
For this input, one possible arrangement is:
o.o
.o.
..o
where each o is a jumping rook.
Sample Input 1
5 10
..#..
..#..
#####
..#..
..#..
Sample Output 1
4
Explanation 1
For this input, one possible arrangement is:
.o#o.
oo#oo
#####
.o#o.
o.#.o
where each o is a jumping rook.
Limbajul de programare folosit: cpp14
Cod:
#include<stdio.h>
#include<stdbool.h>
#define maxn 155
#define maxV 24035
#define maxE 96110
bool area[maxn][maxn];
int hnum[maxn][maxn], vnum[maxn][maxn], vdeg[maxn*maxn], hdeg[maxn*maxn], first[maxV], next[maxE], to[maxE], from[maxE], cap[maxE], cost[maxE], ecnt;
void add_edge(int u, int v, int _cap, int _cost)
{
next[ecnt] = first[u];
to[ecnt] = v;
from[ecnt] = u;
cap[ecnt] = _cap;
cost[ecnt] = _cost;
first[u] = ecnt;
ecnt++;
next[ecnt] = first[v];
to[ecnt] = u;
from[ecnt] = v;
cap[ecnt] = 0;
cost[ecnt] = -_cost;
first[v] = ecnt;
ecnt++;
}
bool inq[maxV];
int q[maxV], dist[maxV], h[maxV];
int push_flow(int S, int T)
{
for( int i = 0 ; i <= T ; i++ )
{
inq[i] = 0, dist[i] = (int)1e9, h[i] = -1;
}
int ql = 0, qr = 0;
dist[S] = 0;
h[S] = -1;
q[qr++] = S;
inq[S] = 1;
while( ql != qr )
{
int cur = q[ql];
inq[cur] = 0;
ql++;
if( ql == maxV )
{
ql = 0;
}
for( int i = first[cur] ; i != -1 ; i = next[i] )
{
if( cap[i] > 0 && dist[to[i]] > dist[cur] + cost[i] )
{
dist[to[i]] = dist[cur] + cost[i];
h[to[i]] = i;
if(!inq[to[i]])
{
q[qr] = to[i];
inq[to[i]] = 1;
qr++;
if( qr == maxV )
{
qr = 0;
}
}
}
}
}
if( dist[T] == (int)1e9 )
{
return -1;
}
int cur = T, pcost = 0;
while( h[cur] != -1 )
{
cap[h[cur]]--;
cap[h[cur]^1]++;
pcost += cost[h[cur]];
cur = from[h[cur]];
}
return pcost;
}
int main()
{
int n, k;
scanf("%d%d", &n, &k);
for( int i = 0 ; i < n ; i++ )
{
for( int j = 0 ; j < n ; j++ )
{
char u[3];
scanf("%1s", u);
if( u[0] == '#' )
{
area[i][j] = 0;
}
else
{
area[i][j] = 1;
}
}
}
int hcnt = 0, vcnt = 0;
for( int i = 0 ; i < n ; i++ )
{
for( int j = 0 ; j < n ; j++ )
{
if(area[i][j])
{
if( j == 0 || !area[i][j-1] )
{
hnum[i][j] = hcnt++;
}
else
{
hnum[i][j] = hnum[i][j-1];
}
}
}
}
for( int j = 0 ; j < n ; j++ )
{
for( int i = 0 ; i < n ; i++ )
{
if(area[i][j])
{
if( i == 0 || !area[i-1][j] )
{
vnum[i][j] = vcnt++;
}
else
{
vnum[i][j] = vnum[i-1][j];
}
}
}
}
int S = hcnt + vcnt, T = hcnt + vcnt + 1;
ecnt = 0;
for( int i = 0 ; i < hcnt ; i++ )
{
hdeg[i] = 0;
}
for( int i = 0 ; i < vcnt ; i++ )
{
vdeg[i] = 0;
}
for( int i = 0 ; i < n ; i++ )
{
for( int j = 0 ; j < n ; j++ )
{
if(area[i][j])
{
hdeg[hnum[i][j]]++, vdeg[vnum[i][j]]++;
}
}
}
for( int i = 0 ; i <= T ; i++ )
{
first[i] = -1;
}
for( int i = 0 ; i < hcnt ; i++ )
{
for( int j = 0 ; j < hdeg[i] ; j++ )
{
add_edge(S, i, 1, j);
}
}
for( int i = 0 ; i < vcnt ; i++ )
{
for( int j = 0 ; j < vdeg[i] ; j++ )
{
add_edge(i+hcnt, T, 1, j);
}
}
for( int i = 0 ; i < n ; i++ )
{
for( int j = 0 ; j < n ; j++ )
{
if(area[i][j])
{
add_edge(hnum[i][j], vnum[i][j] + hcnt, 1, 0);
}
}
}
int res = 0;
for( int i = 0 ; i < k ; i++ )
{
int z = push_flow(S, T);
res += z;
}
printf("%d", res);
return 0;
}
Scor obtinut: 1.0
Submission ID: 464647301
Link challenge: https://www.hackerrank.com/challenges/jumping-rooks/problem