Chef and Robots Competition CodeChef Solution

Problem -Chef and Robots Competition 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.

Chef and Robots Competition CodeChef Solution in C++14

“ ”

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int a[N][N];
int dis1[N][N],dis2[N][N],vis[N][N];
struct NODE{
	int x;
	int y;
};
int n,m,t;
void bfs1(int k)
{
	queue<NODE> q;
	q.push((NODE){1,1});
	vis[1][1]=1;
	dis1[1][1]=0;
	while(!q.empty())
	{
		NODE tmp=q.front();
		q.pop();
		int xx=tmp.x;
		int yy=tmp.y;
		for(int i=-k;i<=k;i++)
		{
			for(int ff=-(k-abs(i));ff<=(k-abs(i));ff++)
			{
				int dx=xx+i;
				int dy=yy+ff;
				if(dx>=1&&dx<=n&&dy>=1&&dy<=m)
				{
					if(a[dx][dy]==0&&vis[dx][dy]==0)
					{
						dis1[dx][dy]=dis1[xx][yy]+1;
						vis[dx][dy]=1;
						q.push((NODE){dx,dy});
					}
				}
			}
		}
	}
}
void bfs2(int k)
{
	queue<NODE> qq;
	qq.push((NODE){1,m});
	vis[1][m]=1;
	dis2[1][m]=0;
	while(!qq.empty())
	{
		NODE tmp=qq.front();
		qq.pop();
		int xx=tmp.x;
		int yy=tmp.y;
		for(int i=-k;i<=k;i++)
		{
			for(int ff=-(k-abs(i));ff<=(k-abs(i));ff++)
			{
				int dx=xx+i;
				int dy=yy+ff;
				if(dx>=1&&dx<=n&&dy>=1&&dy<=m)
				{
					if(a[dx][dy]==0&&vis[dx][dy]==0)
					{
						dis2[dx][dy]=dis2[xx][yy]+1;
						vis[dx][dy]=1;
						qq.push((NODE){dx,dy});
					}
				}
			}
		}
	}
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		memset(dis1,0x3f,sizeof(dis1));
		memset(dis2,0x3f,sizeof(dis2));
		int k1,k2;
		scanf("%d%d%d%d",&n,&m,&k1,&k2);
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				scanf("%d",&a[i][j]);
			}
		}
		bfs1(k1);
		memset(vis,0,sizeof(vis));
		bfs2(k2);
		memset(vis,0,sizeof(vis));
		int minn=1e8+5;
		int ans=0;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				//printf("%d %d\n",dis1[i][j],dis2[i][j]);
				if(a[i][j]==0)
				{
					ans=max(dis1[i][j],dis2[i][j]);
				}
				minn=min(ans,minn);
			}
		}
		if(minn==1e8+5)printf("-1\n");
		else printf("%d\n",minn);
	}
	return 0;
}

Chef and Robots Competition CodeChef Solution in PYTH 3

“ ”

from collections import deque
for _ in range(int(input())):
    n,m,k1,k2 = list(map(int,input().split()))
    arr = [];
    for i in range(n): arr.append(list(map(int,input().split())))
    robo1 = [[-1]*m for i in range(n)]
    robo2 = [[-1]*m for i in range(n)]
    robo1[0][0] = 0; robo2[0][m-1] = 0
    Q = deque([(0,0)])
    while Q:
        i,j = Q.popleft()
        for x in range(max(i-k1,0),min(i+k1+1,n)):
            t = abs(i-x)
            for y in range(max(0,j-k1+t),min(j+k1-t+1,m)):
                if arr[x][y]==0 and robo1[x][y]==-1:
                    robo1[x][y] = robo1[i][j]+1
                    Q.append((x,y))
    Q = deque([(0,m-1)])
    while Q:
        i,j = Q.popleft()
        for x in range(max(i-k2,0),min(i+k2+1,n)):
            t = abs(i-x)
            for y in range(max(0,j-k2+t),min(j+k2-t+1,m)):
                if arr[x][y]==0 and robo2[x][y]==-1:
                    robo2[x][y] = robo2[i][j]+1
                    Q.append((x,y))
    ans = float("inf")
    for i in range(n):
        for j in range(m):
            if robo1[i][j]!=-1 and robo2[i][j]!=-1:
                ans = min(ans,max(robo1[i][j],robo2[i][j]))
    print(-1 if ans==float("inf") else ans) 

Chef and Robots Competition CodeChef Solution in C

“ ”

#include<stdio.h>
int main()
{
    static int t,n,m,i,j,k,k1,k2,x,y,z,ans,a[101][101],b[101][101][4],c[10001][2];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d%d",&n,&m,&k1,&k2);
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                scanf("%d",&a[i][j]);
            }
        }
        if(m==1)
        {
            printf("0\n");
            continue;
        }
        if(k1==0 && k2==0)
        {
            printf("-1\n");
            continue;
        }
        ans=100000;
        b[1][1][0]=0;
        x=1;
        c[0][0]=c[0][1]=b[1][1][1]=1;
        for(i=0;i<x;i++)
        {
            y=c[i][0];
            z=c[i][1];
            for(j=0;j<=k1;j++)
            {
                if(y+j > n)
                    break;
                for(k=z-k1+j;k<=z+k1-j;k++)
                {
                    if(k<=0)
                    {
                        k=0;
                        continue;
                    }
                    if(k>m)
                        break;
                    if(b[y+j][k][0]==0 && b[y+j][k][1]==0 && a[y+j][k]==0)
                    {
                        b[y+j][k][0]=b[y][z][0]+1;
                        b[y+j][k][1]=1;
                        c[x][0]=y+j;
                        c[x][1]=k;
                        x++;
                    }
                }
            }
            for(j=1;j<=k1;j++)
            {
                if(y-j < 1)
                    break;
                for(k=z-k1+j;k<=z+k1-j;k++)
                {
                    if(k<=0)
                    {
                        k=0;
                        continue;
                    }
                    if(k>m)
                        break;
                    if(b[y-j][k][0]==0 && b[y-j][k][1]==0 && a[y-j][k]==0)
                    {
                        b[y-j][k][0]=b[y][z][0]+1;
                        b[y-j][k][1]=1;
                        c[x][0]=y-j;
                        c[x][1]=k;
                        x++;
                    }
                }
            }
        }
        b[1][m][2]=0;
        x=1;
        c[0][0]=b[1][m][3]=1;
        c[0][1]=m;
        for(i=0;i<x;i++)
        {
            y=c[i][0];
            z=c[i][1];
            for(j=0;j<=k2;j++)
            {
                if(y+j > n)
                    break;
                for(k=z-k2+j;k<=z+k2-j;k++)
                {
                    if(k<=0)
                    {
                        k=0;
                        continue;
                    }
                    if(k>m)
                        break;
                    if(b[y+j][k][2]==0 && b[y+j][k][3]==0 && a[y+j][k]==0)
                    {
                        b[y+j][k][2]=b[y][z][2]+1;
                        b[y+j][k][3]=1;
                        c[x][0]=y+j;
                        c[x][1]=k;
                        x++;
                    }
                }
            }
            for(j=1;j<=k2;j++)
            {
                if(y-j < 1)
                    break;
                for(k=z-k2+j;k<=z+k2-j;k++)
                {
                    if(k<=0)
                    {
                        k=0;
                        continue;
                    }
                    if(k>m)
                        break;
                    if(b[y-j][k][2]==0 && b[y-j][k][3]==0 && a[y-j][k]==0)
                    {
                        b[y-j][k][2]=b[y][z][2]+1;
                        b[y-j][k][3]=1;
                        c[x][0]=y-j;
                        c[x][1]=k;
                        x++;
                    }
                }
            }
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                if(a[i][j]==0 && b[i][j][1] && b[i][j][3])
                {
                    x=b[i][j][0];
                    if(b[i][j][2]>b[i][j][0])
                    {
                        x=b[i][j][2];
                    }
                    if(ans>x)
                        ans=x;
                }
                b[i][j][0]=b[i][j][1]=b[i][j][2]=b[i][j][3]=0;
            }
        }
        if(ans==100000)
            printf("-1\n");
        else
            printf("%d\n",ans);
    }
    return 0;
}

Chef and Robots Competition CodeChef Solution in JAVA

“ ”

/* package codechef; // don't place package name! */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

class CHEFARC {

    static class Node {
        int row;
        int col;
        int c;

        public Node(int row, int col, int c) {
            this.row = row;
            this.col = col;
            this.c = c;
        }
    }

    private static int N, M, K1, K2;
    private static int[][] arr;

    private static int[][] A;
    private static int[][] B;

    private static boolean isSafe(int[][] cost, int row, int col, int c) {
        if (row >= 0 && row < N && col >= 0 && col < M && cost[row][col] > c && arr[row][col] == 0) {
            return true;
        }
        return false;
    }
     private static void bfs(int[][] cost, int row, int col, int K) {
        cost[row][col] = 0;
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(row, col, 0));
        while (queue.size() > 0) {
            Node temp = queue.remove();
            for (int i = Math.min(0, Math.abs(temp.row - K)); i < Math.min(temp.row + K + 1, N); i++) {
                for (int j = Math.min(0, Math.abs(temp.col - K)); j < Math.min(temp.col + K + 1, M); j++) {
                    if (Math.abs(temp.row - i) + Math.abs(temp.col - j) > K) continue;
                    if (isSafe(cost, i, j, temp.c + 1)) {
                        cost[i][j] = temp.c + 1;
                        queue.add(new Node(i, j, temp.c + 1));
                    }
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {


        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(reader.readLine());

        while (T-- > 0) {

            String[] inputArr = reader.readLine().split(" ");
            N = Integer.parseInt(inputArr[0]);
            M = Integer.parseInt(inputArr[1]);
            K1 = Integer.parseInt(inputArr[2]);
            K2 = Integer.parseInt(inputArr[3]);
             arr = new int[N][M];
            A = new int[N][M];
            B = new int[N][M];

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    A[i][j] = Integer.MAX_VALUE;
                    B[i][j] = Integer.MAX_VALUE;
                }
            }

            for (int i = 0; i < N; i++) {
                inputArr = reader.readLine().split(" ");
                for (int j = 0; j < M; j++) {
                    arr[i][j] = Integer.parseInt(inputArr[j]);
                }
            }

            bfs(A, 0, 0, K1);
            bfs(B, 0, M - 1, K2);
            

            int ans = Integer.MAX_VALUE;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (A[i][j] != Integer.MAX_VALUE && B[i][j] != Integer.MAX_VALUE && arr[i][j] == 0) {
                        if (ans > Math.max(A[i][j], B[i][j])) {
                            ans = Math.max(A[i][j], B[i][j]);
                        }
                    }
                }
            }
            System.out.println((ans != Integer.MAX_VALUE) ? ans : -1);
        }
    }
}

Chef and Robots Competition CodeChef Solution in PYTH

“ ”

from Queue import Queue

def bfs(n, m, x, y, k, mat):

    inf = float("inf")
    dist = [[inf for _ in xrange(m)] for __ in xrange(n)]
    dist[x][y] = 0
    que = Queue()
    que.put((x, y, 0))
    while (not(que.empty())):
        (x1, y1, a1) = que.get()

        for x_cor in xrange(max(x1 - k, 0), min(x1 + k + 1, n)):
            d = abs(x_cor - x1)
            for y_cor in xrange(max(y1 - k + d, 0), min(y1 + k + 1 - d, m)):
                if (mat[x_cor][y_cor] == 0):
                    if (dist[x_cor][y_cor] == inf):
                        dist[x_cor][y_cor] = a1 + 1
                        que.put((x_cor, y_cor, a1 + 1))

    return dist


tt = int(raw_input())
for i in xrange(tt):
    n, m, k1, k2 = map(int, raw_input().split())
    # mat = [[0 for _ in xrange(m)] for __ in xrange(n)]
    mat = []
    for j in xrange(n):
        mat.append(map(int, raw_input().split()))

    bot1 = bfs(n, m, 0, 0, k1, mat)
    bot2 = bfs(n, m, 0, m - 1, k2, mat)
    glo = float("inf")
    for x in xrange(n):
        for y in xrange(m):
            dur = max(bot1[x][y], bot2[x][y])
            glo = min(glo, dur)

    if (glo < float("inf")):
        print glo

    else:
        print "-1"

Chef and Robots Competition CodeChef Solution in C#

“ ”

using System;
using System.Collections.Generic;

namespace ConsoleApplication3
{
	internal class Program
	{
		public static void Main(string[] args)
		{
			int test = int.Parse(Console.ReadLine());
			while (test-- > 0)
			{
				solve();
			}
		}

		private static void solve()
		{
			string[] spl = Console.ReadLine().Split(' ');
			int n = int.Parse(spl[0]);
			int m = int.Parse(spl[1]);
			int K1 = int.Parse(spl[2]);
			int K2 = int.Parse(spl[3]);
			int[,] field = new int[n, m];
			for (int i = 0; i < n; i++)
			{
				string[] row = Console.ReadLine().Split(' ');
				for (int j = 0; j < m; j++)
				{
					field[i, j] = int.Parse(row[j]);
				}
			}
			if (m == 1)
			{
				Console.WriteLine(0);
				return;
			}
			int[,] dist1 = getDist(n, m, K1, field, 0, 0);
			int[,] dist2 = getDist(n, m, K2, field, 0, m - 1);
			int result = int.MaxValue / 2;
			for (int i = 0; i < n; i++)
				for (int j = 0; j < m; j++)
				{
					int d1 = dist1[i, j];
					int d2 = dist2[i, j];
					int cur = Math.Max(d1, d2);
					result = Math.Min(result, cur);
				}
			if (result >= int.MaxValue / 2)
			{
				Console.WriteLine(-1);
			}
			else
			{
				Console.WriteLine(result);
			}
		}

		private static int[,] getDist(int n, int m, int K, int[,] field, int startY, int startX)
		{
			int[, ] dist = new int[n, m];
			for (int i = 0; i < n; i++)
				for (int j = 0; j < m; j++)
						dist[i, j] = int.MaxValue / 2;

			LinkedList<Item> queue = new LinkedList<Item>();
			dist[startY, startX] = 0;
			queue.AddFirst(new Item(startX, startY));
			while (queue.Count > 0)
			{
				var p = queue.First.Value;
				queue.RemoveFirst();

				for (int nx = p.X - K; nx <= p.X + K; nx++)
					for (int ny = p.Y - K; ny <= p.Y + K; ny++)
					{
						if (Math.Abs(p.X - nx) + Math.Abs(p.Y - ny) > K)
							continue;
					if (nx < 0 || ny < 0 || nx >= m || ny >= n)
						continue;
					if (field[ny, nx] == 1)
						continue;

					if (dist[ny, nx] > dist[p.Y, p.X] + 1)
					{
						dist[ny, nx] = dist[p.Y, p.X] + 1;
						var nextItem = new Item(nx, ny);
						queue.AddLast(nextItem);
					}
				}
			}
			return dist;
		}


		private class Item
		{
			public int X;
			public int Y;

			public Item(int x, int y)
			{
				X = x;
				Y = y;
			}
		}
	}
}

Chef and Robots Competition CodeChef Solution in GO

“ ”

package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
)

var in = bufio.NewReader(os.Stdin)

func readInt() int {
	started := false
	mul := 1
	ret := 0
	for {
		switch b, err := in.ReadByte(); {
		case err != nil && err != io.EOF:
			panic(err)
		case b == '-':
			mul *= -1
		case b >= '0' && b <= '9':
			ret = ret*10 + int(b-'0')
			started = true
		default:
			if started {
				return ret
			}
		}
	}
}

func main() {
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	for t := readInt(); t > 0; t-- {
		fmt.Fprintln(out, solve())
	}
}

func solve() int {
	n := readInt()
	m := readInt()
	k1 := readInt()
	k2 := readInt()
	cell := make([][]int, n)
	for i := range cell {
		cell[i] = make([]int, m)
		for j := range cell[i] {
			cell[i][j] = readInt()
		}
	}
	dist1 := bfs(cell, 0, 0, makeDiffs(k1))
	dist2 := bfs(cell, 0, m-1, makeDiffs(k2))
	ans := n*m + 2
	for i := range dist1 {
		for j := range dist1[i] {
			if dist1[i][j] == -1 || dist2[i][j] == -1 {
				continue
			}
			ans = min(ans, max(dist1[i][j], dist2[i][j]))
		}
	}
	if ans == n*m+2 {
		return -1
	}
	return ans - 1
}

func makeDiffs(k int) [][2]int {
	var res [][2]int
	for i := -k; i <= k; i++ {
		for j := -k; j <= k; j++ {
			if i == 0 && j == 0 || abs(i)+abs(j) > k {
				continue
			}
			res = append(res, [2]int{i, j})
		}
	}
	return res
}

func bfs(cell [][]int, sr, sc int, diffs [][2]int) [][]int {
	q := [][2]int{{sr, sc}}
	res := make([][]int, len(cell))
	for i := range res {
		res[i] = make([]int, len(cell[i]))
		for j := range res[i] {
			if cell[i][j] == 1 {
				res[i][j] = -1
			}
		}
	}
	res[sr][sc] = 1
	for len(q) > 0 {
		v := q[0]
		q = q[1:]
		dist := res[v[0]][v[1]] + 1
		for _, d := range diffs {
			u := [2]int{v[0] + d[0], v[1] + d[1]}
			if u[0] < 0 || u[0] >= len(cell) || u[1] < 0 || u[1] >= len(cell[0]) || res[u[0]][u[1]] != 0 {
				continue
			}
			res[u[0]][u[1]] = dist
			q = append(q, u)
		}
	}
	for i := range res {
		for j := range res[i] {
			if res[i][j] == 0 {
				res[i][j] = -1
			}
		}
	}
	return res
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

Chef and Robots Competition CodeChef Solution Review:

In our experience, we suggest you solve this Chef and Robots Competition 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 Chef and Robots Competition CodeChef Solution.

Find on CodeChef

“ ”

Conclusion:

I hope this Chef and Robots Competition 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