HackerRank Jumping Rooks Problem Solution
In this post, we will solve HackerRank Jumping Rooks Problem Solution.
Nina has an n x n chessboard and k 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 (x, y₁) and the second rook is in cell (x, y) (where y1 y2), then these two rooks beat each other if and only if (x, y), (x, y1 +1),…, (x, y) are free. If the rooks are in cells (x1,y) and (x2,y), then cells (x1,y), (x1+1, y),…, (2, y) must all be free.
Given the configuration of the chessboard and some k, help Nina place k 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 n (the size of the chessboard) and k (the number of rooks to place). Each line of the n subsequent lines contains a string of n characters describing each row in the chessboard. The jth character of the ith line is # if cell (i, j) is blocked or, if the cell
is free.
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.
Jumping Rooks C Solution
#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;
}Jumping Rooks C++ Solution
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
#define INF 1000000000
#define maxn 10002
struct Edge
{
int from, to, cap, flow, cost;
Edge(int u, int v, int c, int f, int w) : from(u), to(v), cap(c), flow(f), cost(w) {}
};
struct MCMF
{
int n, m;
vector<Edge> edges;
vector<int> G[maxn];
int inq[maxn];
int d[maxn];
int p[maxn];
int a[maxn];
void init(int n)
{
this->n = n;
for (int i = 0; i < n; ++i)
{
G[i].clear();
}
edges.clear();
}
void AddEdge(int from, int to, int cap, int cost)
{
edges.push_back(Edge(from, to, cap, 0, cost));
edges.push_back(Edge(to, from, 0, 0, -cost));
m = edges.size();
G[from].push_back(m - 2);
G[to].push_back(m - 1);
}
bool BellmanFord(int s, int t, int & cost)
{
for (int i = 0; i < n; ++i)
{
d[i] = INF;
}
memset(inq, 0, sizeof(inq));
d[s] = 0;
inq[s] = 1;
p[s] = 0;
a[s] = INF;
queue<int> Q;
Q.push(s);
while (!Q.empty())
{
int u = Q.front();
Q.pop();
inq[u] = 0;
for (int i = 0; i < G[u].size(); ++i)
{
Edge & e = edges[G[u][i]];
if (e.cap > e.flow && d[e.to] > d[u] + e.cost)
{
d[e.to] = d[u] + e.cost;
p[e.to] = G[u][i];
a[e.to] = min(a[u], e.cap - e.flow);
if (!inq[e.to])
{
Q.push(e.to);
inq[e.to] = 1;
}
}
}
}
if (d[t] == INF)
{
return false;
}
cost += d[t] * a[t];
for (int u = t; u != s; u = edges[p[u]].from)
{
edges[p[u]].flow += a[t];
edges[p[u] ^ 1].flow -= a[t];
}
return true;
}
int MincostMaxflow(int s, int t)
{
int cost = 0;
while (BellmanFord(s, t, cost));
return cost;
}
};
char s[50][51];
int rid[50][50];
int cid[50][50];
int rcnt, ccnt;
int r[2500], c[2500];
int main()
{
int n, k;
scanf("%d %d", &n, &k);
for (int i = 0; i < n; ++i)
scanf("%s", s[i]);
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
{
if (s[i][j] == '#')
continue;
if (!rid[i][j])
{
++rcnt;
int t = j;
while (t < n && s[i][t] == '.')
{
rid[i][t] = rcnt;
++r[rcnt];
++t;
}
}
if (!cid[i][j])
{
++ccnt;
int t = i;
while (t < n && s[t][j] == '.')
{
cid[t][j] = ccnt;
++c[ccnt];
++t;
}
}
}
MCMF mcmf;
mcmf.init(rcnt + ccnt + 3);
for (int i = 1; i <= rcnt; ++i)
for (int j = 0; j < r[i]; ++j)
mcmf.AddEdge(0, i, 1, j);
for (int i = 1; i <= ccnt; ++i)
for (int j = 0; j < c[i]; ++j)
mcmf.AddEdge(rcnt + i, rcnt + ccnt + 1, 1, j);
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
{
if (s[i][j] == '#')
continue;
mcmf.AddEdge(rid[i][j], rcnt + cid[i][j], 1, 0);
}
mcmf.AddEdge(rcnt + ccnt + 2, 0, k, 0);
printf("%d\n", mcmf.MincostMaxflow(rcnt + ccnt + 2, rcnt + ccnt + 1));
return 0;
}Jumping Rooks Java Solution
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.List;
public class C {
InputStream is;
PrintWriter out;
String INPUT = "";
void solve()
{
int n = ni(), K = ni();
char[][] map = nm(n,n);
int[][] ud = new int[n][n];
int[][] lr = new int[n][n];
int pud = 0, plr = 0;
{
int id = -1;
for(int i = 0;i < n;i++){
char pre = 0;
for(int j = 0;j < n;j++){
if(map[j][i] == '.'){
if(pre != '.')id++;
ud[j][i] = id;
}
pre = map[j][i];
}
}
pud = id + 1;
}
{
int id = -1;
for(int i = 0;i < n;i++){
char pre = 0;
for(int j = 0;j < n;j++){
if(map[i][j] == '.'){
if(pre != '.')id++;
lr[i][j] = id;
}
pre = map[i][j];
}
}
plr = id + 1;
}
List<Edge> es = new ArrayList<>();
for(int i = 0;i < n;i++){
for(int j = 0;j < n;j++){
if(map[i][j] == '.'){
es.add(new Edge(ud[i][j], lr[i][j]+pud, 1, 0));
}
}
}
int src = pud + plr, sink = src + 1;
for(int i = 0;i < pud;i++){
for(int j = 0;j <= n;j++){
es.add(new Edge(src, i, 1, j));
}
}
for(int i = 0;i < plr;i++){
for(int j = 0;j <= n;j++){
es.add(new Edge(i+pud, sink, 1, j));
}
}
out.println(solveMinCostFlow(compileWD(sink+1, es), src, sink, K));
}
public static class Edge
{
public int from, to;
public int capacity;
public int cost;
public int flow;
public Edge complement;
// public int iniflow;
public Edge(int from, int to, int capacity, int cost) {
this.from = from;
this.to = to;
this.capacity = capacity;
this.cost = cost;
}
}
public static Edge[][] compileWD(int n, List<Edge> edges)
{
Edge[][] g = new Edge[n][];
// cloning
for(int i = edges.size()-1;i >= 0;i--){
Edge origin = edges.get(i);
Edge clone = new Edge(origin.to, origin.from, origin.capacity, -origin.cost);
clone.flow = origin.capacity;
clone.complement = origin;
origin.complement = clone;
edges.add(clone);
}
int[] p = new int[n];
for(Edge e : edges)p[e.from]++;
for(int i = 0;i < n;i++)g[i] = new Edge[p[i]];
for(Edge e : edges)g[e.from][--p[e.from]] = e;
return g;
}
// NOT VERIFIED
public static Edge[][] compileWU(int n, List<Edge> edges)
{
Edge[][] g = new Edge[n][];
// cloning
for(int i = edges.size()-1;i >= 0;i--){
Edge origin = edges.get(i);
Edge back = new Edge(origin.to, origin.from, origin.capacity, origin.cost);
edges.add(back);
}
for(int i = edges.size()-1;i >= 0;i--){
Edge origin = edges.get(i);
Edge clone = new Edge(origin.to, origin.from, origin.capacity, -origin.cost);
clone.flow = origin.capacity;
clone.complement = origin;
origin.complement = clone;
edges.add(clone);
}
int[] p = new int[n];
for(Edge e : edges)p[e.from]++;
for(int i = 0;i < n;i++)g[i] = new Edge[p[i]];
for(Edge e : edges)g[e.from][--p[e.from]] = e;
return g;
}
public static long solveMinCostFlow(Edge[][] g, int source, int sink, long all)
{
int n = g.length;
long mincost = 0;
int[] potential = new int[n];
final int[] d = new int[n];
MinHeap q = new MinHeap(n);
while(all > 0){
// shortest path src->sink
Edge[] inedge = new Edge[n];
Arrays.fill(d, Integer.MAX_VALUE / 2);
d[source] = 0;
q.add(source, 0);
while(q.size() > 0){
int cur = q.argmin();
q.remove(cur);
for(Edge ne : g[cur]){
if(ne.capacity - ne.flow > 0){
int nd = d[cur] + ne.cost + potential[cur] - potential[ne.to];
if(d[ne.to] > nd){
inedge[ne.to] = ne;
d[ne.to] = nd;
q.update(ne.to, nd);
}
}
}
}
if(inedge[sink] == null)break;
long minflow = all;
long sumcost = 0;
for(Edge e = inedge[sink];e != null;e = inedge[e.from]){
if(e.capacity - e.flow < minflow)minflow = e.capacity - e.flow;
sumcost += e.cost;
}
mincost += minflow * sumcost;
for(Edge e = inedge[sink];e != null;e = inedge[e.from]){
e.flow += minflow;
e.complement.flow -= minflow;
}
all -= minflow;
for(int i = 0;i < n;i++){
potential[i] += d[i];
}
}
return mincost;
}
public static class MinHeap {
public int[] a;
public int[] map;
public int[] imap;
public int n;
public int pos;
public static int INF = Integer.MAX_VALUE;
public MinHeap(int m)
{
n = m+2;
a = new int[n];
map = new int[n];
imap = new int[n];
Arrays.fill(a, INF);
Arrays.fill(map, -1);
Arrays.fill(imap, -1);
pos = 1;
}
public int add(int ind, int x)
{
int ret = imap[ind];
if(imap[ind] < 0){
a[pos] = x; map[pos] = ind; imap[ind] = pos;
pos++;
up(pos-1);
}
return ret != -1 ? a[ret] : x;
}
public int update(int ind, int x)
{
int ret = imap[ind];
if(imap[ind] < 0){
a[pos] = x; map[pos] = ind; imap[ind] = pos;
pos++;
up(pos-1);
}else{
int o = a[ret];
a[ret] = x;
up(ret);
down(ret);
// if(a[ret] > o){
// up(ret);
// }else{
// down(ret);
// }
}
return x;
}
public int remove(int ind)
{
if(pos == 1)return INF;
if(imap[ind] == -1)return INF;
pos--;
int rem = imap[ind];
int ret = a[rem];
map[rem] = map[pos];
imap[map[pos]] = rem;
imap[ind] = -1;
a[rem] = a[pos];
a[pos] = INF;
map[pos] = -1;
up(rem);
down(rem);
return ret;
}
public int min() { return a[1]; }
public int argmin() { return map[1]; }
public int size() { return pos-1; }
private void up(int cur)
{
for(int c = cur, p = c>>>1;p >= 1 && a[p] > a[c];c>>>=1, p>>>=1){
int d = a[p]; a[p] = a[c]; a[c] = d;
int e = imap[map[p]]; imap[map[p]] = imap[map[c]]; imap[map[c]] = e;
e = map[p]; map[p] = map[c]; map[c] = e;
}
}
private void down(int cur)
{
for(int c = cur;2*c < pos;){
int b = a[2*c] < a[2*c+1] ? 2*c : 2*c+1;
if(a[b] < a[c]){
int d = a[c]; a[c] = a[b]; a[b] = d;
int e = imap[map[c]]; imap[map[c]] = imap[map[b]]; imap[map[b]] = e;
e = map[c]; map[c] = map[b]; map[b] = e;
c = b;
}else{
break;
}
}
}
}
void run() throws Exception
{
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
}
public static void main(String[] args) throws Exception { new C().run(); }
private byte[] inbuf = new byte[1024];
private int lenbuf = 0, ptrbuf = 0;
private int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private double nd() { return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }
private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}
