Queens on Board – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Queens on Board HackerRank Solution
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <fstream>
#include <ctime>
#include <deque>
#include <bitset>
#include <cctype>
#include <utility>
#include <cassert>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;
#define Rep(i,n) for(int i = 0; i < (n); ++i)
#define Repd(i,n) for(int i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(int i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(int i = (a); i >= (b); --i)
#define Fit(i,v) For(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
#define Fitd(i,v) For(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define ms(a,x) memset(a, x, sizeof(a))
template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; }
template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> T sqr(T x) { return x * x; }
template<class T> T cube(T x) { return x * x * x; }
template<class T> int getbit(T s, int i) { return (s >> i) & 1; }
template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
template<class T> int cntbit(T s) { return __builtin_popcount(s); }
const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0;int ptr = 0;
char gc() { if (rsz <= 0) { ptr = 0; rsz = (int) fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; }
void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); }
int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; }
template<class T> bool gi(T &v) {
v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc();
while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true;
}
typedef pair<int, int> II;
const ld PI = acos(ld(-1.0));
const ld eps = 1e-9;
const int inf = (int)1e9 + 5;
const ll linf = (ll)1e17 + 5;
int dr[8] = {-1, +1, 0, 0, +1, +1, -1, -1};
int dc[8] = {0, 0, +1, -1, -1, +1, -1, +1};
const int mod = 1000000007;
#define maxn 1000005
int n, m;
int f[55][1 << 5][1 << 5][1 << 5];
int nex[3][1 << 5], a[105], b[105];
string s[105];
bool can[1 << 5][1 << 5];
int cal0(int A){
return A;
}
int cal1(int A, int num){
int res = 0;
For(i, 1, num - 1) if(getbit(A, i)) res = onbit(res, i - 1);
return res;
}
int cal2(int A, int num){
int res = 0;
For(i, 0, num - 2) if(getbit(A, i)) res = onbit(res, i + 1);
return res;
}
void add(int &a, int b){
a += b;
if(a >= mod) a -= mod;
}
void solve(){
cin >> n >> m;
Rep(mask, (1 << m)){
nex[0][mask] = mask;
nex[1][mask] = cal1(mask, m);
nex[2][mask] = cal2(mask, m);
}
ms(can, 0);
Rep(mask, 1 << m){
Rep(M, 1 << m) if((mask & M) == M){
can[mask][M] = 1;
Rep(i, m) For(j, i + 1, m - 1) if(getbit(M, i) & getbit(M, j)){
bool ok = false;
For(k, i, j) if(!getbit(mask, k)) ok = true;
if(!ok) can[mask][M] = 0;
}
}
}
ms(f, 0); f[0][0][0][0] = 1;
Rep(i, n) {
cin >> s[i];
a[i] = 0;
b[i] = 0;
Rep(j, m) {
if(s[i][j] == '.') a[i] = onbit(a[i], j);
else b[i] = onbit(b[i], j);
}
}
Rep(i, n) Rep(mask1, (1 << m)) Rep(mask2, (1 << m)) Rep(mask3, (1 << m)) if(f[i][mask1][mask2][mask3]){
int M1, M2, M3;
int mask = (mask1 | mask2 | mask3);
Rep(m, (1 << m)) if(can[a[i]][m] && (mask & m) == 0){
M1 = nex[0][(mask1 | m) & a[i]];
M2 = nex[1][(mask2 | m) & a[i]];
M3 = nex[2][(mask3 | m) & a[i]];
add(f[i + 1][M1][M2][M3], f[i][mask1][mask2][mask3]);
}
}
int res = -1;
Rep(mask1, (1 << m)) Rep(mask2, (1 << m)) Rep(mask3, (1 << m)) {
add(res, f[n][mask1][mask2][mask3]);
}
cout << res << endl;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("in.txt", "r", stdin);
int test;
cin >> test;
Rep(itest, test){
solve();
}
return 0;
}
Java Queens on Board HackerRank Solution
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class Solution {
static InputStream is;
static PrintWriter out;
static String INPUT = "";
static void solve()
{
for(int T = ni();T >= 1;T--){
int n = ni(), m = ni();
char[][] map = nm(n,m);
int[][][] pre = new int[1<<m][1<<m-1][1<<m-1];
int[][][] cur = new int[1<<m][1<<m-1][1<<m-1];
pre[0][0][0] = 1;
int mod = 1000000007;
for(int i = 0;i < n;i++){
for(int j = 0;j < 1<<m;j++){
for(int k = 0;k < 1<<m-1;k++){
for(int l = 0;l < 1<<m-1;l++){
cur[j][k][l] = 0;
}
}
}
int[] puts = new int[1<<m];
int pp = 0;
int block = 0;
for(int j = 0;j < m;j++){
if(map[i][j] == '#')block|=1<<j;
}
inner:
for(int put = 0;put < 1<<m;put++){
if((put&block) != 0)continue;
boolean blocked = true;
for(int j = 0;j < m;j++){
if(put<<31-j<0){
if(!blocked)continue inner;
blocked = false;
}else if(map[i][j] == '#'){
blocked = true;
}
}
puts[pp++] = put;
}
for(int j = 0;j < 1<<m;j++){
for(int k = 0;k < 1<<m-1;k++){
for(int l = 0;l < 1<<m-1;l++){
if(pre[j][k][l] == 0)continue;
int ng = j|k<<1|l;
for(int u = 0;u < pp;u++){
int put = puts[u];
if((put&ng) != 0)continue;
int nj = (j|put)&~block;
int nk = (k<<1|put)&~block&(1<<m-1)-1;
int nl = ((l|put)&~block)>>>1;
cur[nj][nk][nl] += pre[j][k][l];
if(cur[nj][nk][nl] >= mod)cur[nj][nk][nl] -= mod;
}
}
}
}
int[][][] dum = cur; cur = pre; pre = dum;
}
long ret = mod-1;
for(int j = 0;j < 1<<m;j++){
for(int k = 0;k < 1<<m-1;k++){
for(int l = 0;l < 1<<m-1;l++){
ret += pre[j][k][l];
}
}
}
out.println(ret%mod);
}
}
public static void main(String[] args) throws Exception
{
long S = System.currentTimeMillis();
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
solve();
out.flush();
long G = System.currentTimeMillis();
tr(G-S+"ms");
}
private static boolean eof()
{
if(lenbuf == -1)return true;
int lptr = ptrbuf;
while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;
try {
is.mark(1000);
while(true){
int b = is.read();
if(b == -1){
is.reset();
return true;
}else if(!isSpaceChar(b)){
is.reset();
return false;
}
}
} catch (IOException e) {
return true;
}
}
private static byte[] inbuf = new byte[1024];
static int lenbuf = 0, ptrbuf = 0;
private static 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 static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private static double nd() { return Double.parseDouble(ns()); }
private static char nc() { return (char)skip(); }
private static 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 static 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 static 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 static int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private static 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 static 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) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}
Python 3 Queens on Board HackerRank Solution
def memoize(func):
pool = {}
def wrapper(*arg):
if arg not in pool:
pool[arg] = func(*arg)
return pool[arg]
return wrapper
mod = 1000000007
for case in range(int(input())):
Y,X = map(int,input().split())
mx = [int(''.join('0' if c =='.' else '1' for c in input().rstrip()), 2) for i in range(Y)]
full = (1<<X)-1
def is_wall(x,y):
return mx[y] & (1<<x) != 0 if 0<=x<X and 0<=y<Y else True
def get_free(mx):
y = 0
while y<Y and mx[y] == full:
y+=1
if y==Y: return (None,None)
free = 0
while mx[y] & (1<<free) != 0:
free += 1
if free >= X: return (None,None)
return (free,y)
def place_queen(x,y,mx):
nmx = list(mx)
for dx in [-1,0,1]:
for dy in [-1,0,1]:
if dx == 0 and dy == 0: continue
cx,cy = x,y
while not is_wall(cx,cy):
nmx[cy] |= (1<<cx)
cx,cy = cx+dx,cy+dy
return tuple(nmx)
@memoize
def rec(mx):
free_x,free_y = get_free(mx)
if free_x == None: return 0
#ignore free place
imx = list(mx)
imx[free_y] |= 1<<free_x
ans = rec(tuple(imx))
#place queen to free
nmx = place_queen(free_x,free_y,mx)
ans += 1
free_x,free_y = get_free(nmx)
if free_x != None:
ans += rec(nmx)
return ans % mod
print(rec(tuple(mx)))
Python 2 Queens on Board HackerRank Solution
MOD = 1000000007
BLOCK = '#'
def row_placements(empty):
m = len(empty)
blocks = [i for i in xrange(m) if not empty[i]]
segs = zip([0] + [b + 1 for b in blocks], blocks + [m])
def positions(segs):
if len(segs) == 0: return [[]]
beg, end = segs[0]
pp = []
for p in positions(segs[1:]):
for i in xrange(beg, end):
pp.append([i] + p)
pp.append(p)
return pp
def placement(pp):
qrow = [False] * m
for p in pp:
qrow[p] = True
return qrow
return [(p, placement(p)) for p in positions(segs)]
def threaten(attack, m, positions):
def threaten_one(attack, q):
col, diag1, diag2 = attack
return col[q] or diag1[q] or diag2[q]
return any(threaten_one(attack, p) for p in positions)
def advance_attack(attack, empty, qrow):
m = len(empty)
col, diag1, diag2 = attack
new_col = [qrow[i] or (col[i] and empty[i]) for i in xrange(m)]
new_diag1 = [qrow[i + 1] or (diag1[i + 1] and empty[i + 1]) for i in xrange(m - 1)] + [False]
new_diag2 = [False] + [qrow[i - 1] or (diag2[i - 1] and empty[i - 1]) for i in xrange(1, m)]
return tuple(new_col), tuple(new_diag1), tuple(new_diag2)
def advance(attacks, empty):
m = len(empty)
new_attacks = {}
placements = row_placements(empty)
for a in attacks:
for p in placements:
pos, qrow = p
if not threaten(a, m, pos):
new_attack = advance_attack(a, empty, qrow)
if new_attack in new_attacks:
new_attacks[new_attack] += attacks[a]
else:
new_attacks[new_attack] = attacks[a]
return new_attacks
def solve(board):
m = len(board[0])
empty_cells = [[c != BLOCK for c in row] for row in board]
no_attack = ((False,) * m, (False,) * m, (False,) * m)
attacks = {no_attack: 1}
for empty in empty_cells:
attacks = advance(attacks, empty)
return (sum(attacks.values()) - 1) % MOD
if __name__ == "__main__":
def read_ints(): return map(int, raw_input().split())
def main():
for _ in xrange(input()):
n, _m = read_ints()
board = [raw_input() for _i in xrange(n)]
print solve(board)
main()
C Queens on Board HackerRank Solution
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include <stdio.h>
#define MAX_N 50
#define MAX_M 5
#define MAX_CACHE 1000
typedef struct cache_data cache_data;
struct cache_data {
char b[MAX_N * MAX_M + 1];
int s, v; /* safe cells, value */
cache_data *next;
};
cache_data cache[MAX_CACHE];
int solv(char *b, int n, int m) {
}
void init_cache() {
int i;
for (i = 0; i < MAX_CACHE; i++) {
cache[i].next = NULL;
}
}
void clear_cache() {
int i;
cache_data *p, *next;
for (i = 0; i < MAX_CACHE; i++) {
for (p = cache[i].next; p; p = next) {
next = p->next;
free(p);
}
cache[i].next = NULL;
}
}
unsigned int calc_cache_key(char *b) {
unsigned int k = 0;
char *p = b;
for (; *p; p++) {
k *= 23;
if (*p == '.') k += 1;
else k += 2;
}
return k % MAX_CACHE;
}
int get_cache(char *b, int s) {
cache_data *p = cache[calc_cache_key(b)].next;
for (; p; p = p->next) {
if (s == p->s && strcmp(b, p->b) == 0) return p->v;
}
return -1;
}
int main() {
int t, n, m, i, j;
char b[MAX_N * MAX_M + 1];
scanf("%d", &t);
init_cache();
for (i = 0; i < t; i++) {
scanf("%d %d", &n, &m);
for (j = 0; j < n; j++) {
scanf("%s\n", b + j * m);
}
printf("%d\n", solv(b, n, m) % 1000000007);
clear_cache();
}
return 0;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below