N Knights Problem CodeChef Solution

Problem -N Knights Problem CodeChef Solution

This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.

N Knights Problem CodeChef Solution in C++14

#include<bits/stdc++.h>
#define int long long
#define MAXN 50010
#define MAXM 500010
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int dx[8]={1,2,2,1,-1,-2,-2,-1};
const int dy[8]={2,1,-1,-2,-2,-1,1,2};
int T,n,m;
char mp[1010][1010];
struct Node{int to,nxt,flow;}Edge[MAXM];
int Head[MAXN],cnt_Edge=1;
void add(int u,int v,int w){
	Edge[++cnt_Edge]=(Node){v,Head[u],w};
	Head[u]=cnt_Edge;
}
void Add_Edge(int u,int v,int w){add(u,v,w);add(v,u,0);}
int cur[MAXN],dep[MAXN],q[MAXN],l,r;
bool bfs(int s,int t){
	q[l=r=1]=s;memset(dep,0,sizeof(dep));
	dep[s]=1;memcpy(cur,Head,sizeof(cur));
	while(l<=r){
		int u=q[l++];
		for(int i=Head[u];i;i=Edge[i].nxt){
			int v=Edge[i].to,w=Edge[i].flow;
			if(!w||dep[v])continue;
			dep[v]=dep[u]+1;q[++r]=v;
			if(v==t)return true;
		}
	}return false;
}
int dfs(int u,int t,int flow){
	int rest=flow;if(u==t)return flow;
	for(int i=cur[u];i&&rest;i=Edge[i].nxt){
		cur[u]=i;int v=Edge[i].to,w=Edge[i].flow;
		if(!w||dep[v]!=dep[u]+1)continue;
		int now=dfs(v,t,min(rest,w));
		if(!now)dep[v]=-1;
		rest-=now;Edge[i].flow-=now;
		Edge[i^1].flow+=now;
	}return flow-rest;
}
int dinic(int s,int t){
	int ret=0;
	while(bfs(s,t)){
		int flow=0;
		while((flow=dfs(s,t,inf)))
			ret+=flow;
	}return ret;
}
int get(int x,int y){return (x-1)*m+y;}
signed main(){
	scanf("%lld",&T);
	while(T--){
		memset(Head,0,sizeof(Head));cnt_Edge=1;
		scanf("%lld%lld",&n,&m);int cnt=0;
		for(int i=1;i<=n;i++)scanf("%s",mp[i]+1);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++){
				int u=get(i,j);if(mp[i][j]=='#')continue;cnt++;
				if(!((i+j)&1))continue;
				for(int d=0;d<8;d++){
					int x=i+dx[d],y=j+dy[d];
					if(x>0&&x<=n&&y>0&&y<=m&&mp[x][y]=='.')Add_Edge(u,get(x,y),1);
				}
			}
		int s=n*m+1,t=s+1;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++){
			if(mp[i][j]=='#')continue;
			if((i+j)&1)Add_Edge(s,get(i,j),1);
			else Add_Edge(get(i,j),t,1);
		}
		printf("%lld\n",cnt-dinic(s,t));
	}
	return 0;
}

N Knights Problem CodeChef Solution in PYTH 3

# cook your dish here
import random

dy = [-2, -1, 1, 2, -2, -1, 1, 2]
dx = [-1, -2, -2, -1, 1, 2, 2, 1]

class Ponies:
	mat = []
	G = []
	match = []
	used = []

	def dfs(self, v):
		global used

		used.add(v)
		for i in range(len(G[v])):
			u = G[v][i]
			w = match[u]

			if w < 0 or w not in used and self.dfs(w):
				match[v] = u
				match[u] = v

				return 1

		return 0

	def bipartiteMatching(self, V):
		global used
		global match

		res = 0
		match = [-1] * 1500

		for v in range(V):
			if match[v] < 0:
				used = set([])
				if self.dfs(v):
					res += 1

		return res

	def maxIndependentSet(self, h, w, V):
		global G

		G = [[] for _ in range(1500)]
		for i in range(h):
			for j in range(w):
				if mat[i][j] == -1:
					continue

				curr = mat[i][j]
				for k in range(8):
					y = i + dy[k]
					x = j + dx[k]

					if y < 0 or y >= h or x < 0 or x >= w or mat[y][x] == -1:
						continue

					G[curr] += [mat[y][x]]

		maximalIndependentSet = V - self.bipartiteMatching(V)

		return maximalIndependentSet

	def solve(self, chessboard):
		global mat
		
		V = 0
		mat = [[0 for _ in range(50)] for _ in range(50)]

		h = len(chessboard)
		w = len(chessboard[0])

		for i in range(h):
			for j in range(w):
				if chessboard[i][j] == '.':
					V += 1
					mat[i][j] = V
				else:
					mat[i][j] = -1 # wall

		return self.maxIndependentSet(h, w, V)

# TEST_CASES = 90

# MIN_WIDTH =25
# MAX_WIDTH = 30

# MIN_HEIGHT = 25
# MAX_HEIGHT = 30

solver = Ponies()

# def generate_test_case():
# 	h = random.randint(MIN_HEIGHT, MAX_HEIGHT)
# 	w = random.randint(MIN_WIDTH, MAX_WIDTH)

# 	allowed_chars = ['#', '.']
# 	input_mat = []

# 	for _ in range(h):
# 		row = ''
# 		for _ in range(w):
# 			char_idx = random.randint(0, 1)
# 			row += allowed_chars[char_idx]
# 		input_mat += [row]

# 	solution = solver.solve(input_mat)

# 	test_case = '{\"' + '\",\"'.join(input_mat) + '\"},' + str(solution)
# 	print(test_case)

# for _ in range(TEST_CASES):
# 	generate_test_case()

T = int(input())
while T:
	T -= 1

	h, w = [int(entry) for entry in input().split(' ')]

	input_mat = []
	for _ in range(h):
		row = input()
		input_mat += [row]

	print(solver.solve(input_mat))

N Knights Problem CodeChef Solution in C

#include <stdio.h>
#include <string.h>
#define S(a) memset(a,0,sizeof(a));
#define T(a,b) for(a=0;a<b;a++)
#define U(a,b,c) for(a=1;a<=(n*m-1)/2+1;a++)if(b)c
 
int id, xi[8]={-2,-1,1,2,2,1,-1,-2},yi[8]={1,2,2,1,-1,-2,-2,-1}, X[6][9100];
 
int A(int x)
{
int i=X[0][x];
if(X[3][x]==id) return 0;
for(X[3][x]=id; i; i=X[4][i])
	if(!X[1][X[5][i]]||A(X[1][X[5][i]]))
		return 1+(X[2][X[1][X[5][i]]=x]=X[5][i])*0;
return 0;
}
 
main()
{
int fall, i, j, l, x, y, n, m, e, v, d[33][33];
char a[33][33];
for(scanf("%d",&fall); fall--; printf("%d\n", v))
	{
	for(i=!scanf("%d %d\n",&n,&m); i<n; gets(a[i++]));
	S(X[0])S(X[1])S(X[2])S(X[3])
	for(i=e=v=0;i<n;i++)T(j,m)d[i][j]=(i*m+j)/2+1+(v+=a[i][j]!='#')*0;
	T(i,n)T(j,m)if(a[i][j]!='#'&&((i+j)&1))T(l,8)if(!(a[x=i+xi[l]][y=j+yi[l]]=='#'||x<0||y<0||n<=x||m<=y))
	X[1][d[x][y]]=((!!(X[5][++e]=d[x][y])||!X[5][e])&&(!!(X[4][e]=X[0][d[i][j]])||!X[4][e])&&(!!(X[0][d[i][j]]=e)||!e)&&!X[2][d[i][j]]&&!X[1][d[x][y]])?(d[i][j]+(X[2][d[i][j]]=d[x][y])*0):X[1][d[x][y]];
	U(id,!X[2][id],A(id));
	U(i,X[2][i],v--);
	}
return 0;
}
 

N Knights Problem CodeChef Solution in JAVA

import java.util.*;
import java.io.*;
import static java.lang.Math.*;
 
public class Main{
    public static void main(String[] args){
        try{
            new Main().run();
        }catch (Exception e){
 
        }
    }
 
    void run() throws Exception{
        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));//new Scanner(System.in);
        int T = Integer.parseInt(sc.readLine());
        final int[] dx = new int[]{2,1,-1,-2,-2,-1,1,2};
        final int[] dy = new int[]{1,2,2,1,-1,-2,-2,-1};
        for(;T>0;T--){
            String[] hw = sc.readLine().split(" ");
            int h = Integer.parseInt(hw[0]);
            int w = Integer.parseInt(hw[1]);
            int total = h*w;
            char[][] f = new char[h][w];
            for(int i = 0; i < h; i++)f[i] = sc.readLine().toCharArray();
            int[][] id = new int[h][w];
            int count = 1;
            for(int i = 0; i < h; i++)for(int j = 0; j < w; j++)if(f[i][j] == '.')id[i][j] = count++;
            count++;
            V[] nodes = new V[count];
            int[][] graph = new int[count][count];
            for(int i = 0; i < count; i++)nodes[i] = new V();
            for(int i = 0; i < h; i++)
                for(int j = 0; j < w; j++){
                    if(f[i][j] == '.'){
                        int ind = id[i][j];
                        boolean left = (i+j) % 2 == 0;
                        for(int k = 0; k < dx.length; k++){
                            int ny = i + dy[k];
                            int nx = j + dx[k];
                            if(ny < 0 || ny >= h || nx < 0 || nx >= w || f[ny][nx] == '#')
                                continue;
                            int jnd = id[ny][nx];
                            //nodes[ind].add(nodes[jnd], 1);
                            if(left)graph[ind][jnd] = 1;
                            else graph[jnd][ind] = 1;
                        }
                        if(left)
                            graph[0][ind] = 1;
                        else
                            graph[ind][count-1] = 1;
                    }
                }
 
            for(int i = 0; i < count; i++)
                for(int j = 0; j < count; j++)
                    if(graph[i][j] == 1){
                        nodes[i].add(nodes[j], 1);
                    }
 
            int match = SDinic.dinic(nodes[0], nodes[count-1]);
            System.out.println(count-2-match);
        }
    }
}
 
 
class SDinic{
 
    static final int INF = Integer.MAX_VALUE;
 
    static int dinic(V s, V t){
        int flow = 0;
        for(int p = 1; ; p++){
            Queue<V> que = new LinkedList<V>();
            s.level = 0;
            s.p = p;
            que.offer(s);
            while(!que.isEmpty()){
                V v = que.poll();
                v.iter = v.es.size()-1;
                for(E e : v.es)
                    if(e.to.p < p && e.cap > 0){
                        e.to.level = v.level + 1;
                        e.to.p = p;
                        que.offer(e.to);
                    }
            }
            if(t.p < p)
                return flow;
            for(int f; (f = dfs(s, t, INF)) > 0;)
                flow += f;
        }
    }
 
    static int dfs(V v, V t, int f){
        if(v == t)
            return f;
        for(; v.iter >= 0; v.iter--){
            E e = v.es.get(v.iter);
            if(v.level < e.to.level && e.cap > 0){
                int d = dfs(e.to, t, Math.min(f, e.cap));
                if(d > 0){
                    e.cap -= d;
                    e.rev.cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
}
 
class V{
    ArrayList<E> es = new ArrayList<E>();
    int level, p, iter;
    void add(V to, int cap){
        E e = new E(to, cap), rev = new E(this, 0);
        e.rev = rev; rev.rev = e;
        es.add(e); to.es.add(rev);
    }
}
 
class E{
    V to;
    E rev;
    int cap;
    E(V to, int cap){
        this.to = to;
        this.cap = cap;
    }
}

N Knights Problem CodeChef Solution in GO

package main

import (
	"bufio"
	"bytes"
	"fmt"
	"os"
)

func readInt(bytes []byte, from int, val *int) int {
	i := from
	sign := 1
	if bytes[i] == '-' {
		sign = -1
		i++
	}
	tmp := 0
	for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
		tmp = tmp*10 + int(bytes[i]-'0')
		i++
	}
	*val = tmp * sign
	return i
}

func readNum(reader *bufio.Reader) (a int) {
	bs, _ := reader.ReadBytes('\n')
	readInt(bs, 0, &a)
	return
}

func readTwoNums(reader *bufio.Reader) (a int, b int) {
	res := readNNums(reader, 2)
	a, b = res[0], res[1]
	return
}

func readThreeNums(reader *bufio.Reader) (a int, b int, c int) {
	res := readNNums(reader, 3)
	a, b, c = res[0], res[1], res[2]
	return
}

func readNNums(reader *bufio.Reader, n int) []int {
	res := make([]int, n)
	x := 0
	bs, _ := reader.ReadBytes('\n')
	for i := 0; i < n; i++ {
		for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
			x++
		}
		x = readInt(bs, x, &res[i])
	}
	return res
}

func readUint64(bytes []byte, from int, val *uint64) int {
	i := from

	var tmp uint64
	for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
		tmp = tmp*10 + uint64(bytes[i]-'0')
		i++
	}
	*val = tmp

	return i
}

func main() {
	reader := bufio.NewReader(os.Stdin)

	var buf bytes.Buffer

	tc := readNum(reader)

	for tc > 0 {
		tc--
		m, n := readTwoNums(reader)
		G := make([][]byte, m)
		for i := 0; i < m; i++ {
			G[i], _ = reader.ReadBytes('\n')
		}
		res := solve(m, n, G)
		buf.WriteString(fmt.Sprintf("%d\n", res))
	}
	fmt.Print(buf.String())
}

func solve(m, n int, G [][]byte) int {
	N := m * n
	g := NewGraph(N, N*N)

	connect := func(u, v int) {
		a, b := u/n, u%n
		if (a^b)&1 == 1 {
			g.AddEdge(u, v)
		} else {
			g.AddEdge(v, u)
		}
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if G[i][j] == '#' {
				continue
			}
			if i+1 < m && j+2 < n && G[i+1][j+2] == '.' {
				u := i*n + j
				v := (i+1)*n + j + 2
				connect(u, v)
			}
			if i+1 < m && j-2 >= 0 && G[i+1][j-2] == '.' {
				u := i*n + j
				v := (i+1)*n + j - 2
				connect(u, v)
			}
			if i+2 < m && j+1 < n && G[i+2][j+1] == '.' {
				u := i*n + j
				v := (i+2)*n + j + 1
				connect(u, v)
			}
			if i+2 < m && j-1 >= 0 && G[i+2][j-1] == '.' {
				u := i*n + j
				v := (i+2)*n + j - 1
				connect(u, v)
			}
		}
	}
	pair := make([]int, N)
	for i := 0; i < N; i++ {
		pair[i] = -1
	}
	seen := make([]int, N)
	var dfs func(u int, cur int) bool
	dfs = func(u int, cur int) bool {
		if seen[u] == cur {
			return false
		}
		seen[u] = cur
		for i := g.nodes[u]; i > 0; i = g.next[i] {
			v := g.to[i]
			if pair[v] < 0 || dfs(pair[v], cur) {
				pair[v] = u
				return true
			}
		}
		return false
	}
	var res int
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if G[i][j] == '.' {
				res++
				if (i^j)&1 == 1 && pair[i*n+j] < 0 && dfs(i*n+j, i*n+j+1) {
					res--
				}
			}

		}
	}

	return res
}

type Graph struct {
	nodes []int
	next  []int
	to    []int
	cur   int
}

func NewGraph(n int, e int) *Graph {
	nodes := make([]int, n)
	next := make([]int, e+10)
	to := make([]int, e+10)
	return &Graph{nodes, next, to, 0}
}

func (g *Graph) AddEdge(u, v int) {
	g.cur++
	g.next[g.cur] = g.nodes[u]
	g.nodes[u] = g.cur
	g.to[g.cur] = v
}
N Knights Problem CodeChef Solution Review:

In our experience, we suggest you solve this N Knights Problem CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the N Knights Problem CodeChef Solution.

Find on CodeChef

Conclusion:

I hope this N Knights Problem CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

Cognitive Class Answer

CodeChef Solution

Microsoft Learn

Leave a Reply

Your email address will not be published. Required fields are marked *