HackerRank Jumping Rooks Problem Solution Yashwant Parihar, May 21, 2023May 28, 2024 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 FormatThe 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 cellis 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 0For 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 1For this input, one possible arrangement is: .o#o. oo#oo ##### .o#o. o.#.o where each o is a jumping rook. HackerRank Jumping Rooks Problem Solution 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)); } } c C++ HackerRank Solutions java CcppHackerrank Solutionsjava