304 North Cardinal St.
Dorchester Center, MA 02124

# Chef and Robots Competition CodeChef Solution

## 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.IOException;
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;
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 {

while (T-- > 0) {

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++) {
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)
{
while (test-- > 0)
{
solve();
}
}

private static void solve()
{
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++)
{
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;

dist[startY, startX] = 0;
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);
}
}
}
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"
)

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 {
cell := make([][]int, n)
for i := range cell {
cell[i] = make([]int, m)
for j := range cell[i] {
}
}
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!