Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Under the Tunnels CodeChef Solution
Problem -Under the Tunnels 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.
Under the Tunnels CodeChef Solution in C++14
“#include <bits/stdc++.h>
using namespace std;
void sol(){
int n, k;
cin >> n >> k;
vector< vector<int>> graph(n);
for(int i=0; i<n; i++){
string temp;
cin>>temp;
for(int j=0; j<n; j++){
if(temp[j]=='1' && abs(i-j)<=k){
graph[j].push_back(i);
}
}
}
queue<int> q;
vector<int> dist(n,-1);
q.push(n-1);
dist[n-1]=0;
while(!q.empty()){
int node = q.front(); q.pop();
for(auto &i:graph[node]){
if(dist[i] == -1){
dist[i] = dist[node] + 1;
q.push(i);
}
}
}
cout<<dist[0]<<"\n";
}
int main(){
int x;
cin>>x;
while(x--)
{
sol();
}
return 0;
}Under the Tunnels CodeChef Solution in PYTH 3
“# cook your dish here
# cook your dish here
from collections import *
for t in range(int(input())):
n,k = map(int,input().split())
susjedi = defaultdict(list)
for i in range(n):
s = input()
for j in range(n):
if abs(i-j) <= k and s[j] == '1' and i!=j:
susjedi[i].append(j)
def bfs(x):
udaljenost=[-1]*(n)
udaljenost[x]=0
q=deque()
q.append(x)
while len(q)>0:
x=q.popleft()
for y in susjedi[x]:
if udaljenost[y]==-1:
udaljenost[y]=udaljenost[x]+1
q.append(y)
return udaljenost[n-1]
print(bfs(0))Under the Tunnels CodeChef Solution in C
“#include <stdio.h>
int main(void) {
// your code goes here
int t;
scanf("%d",&t);
while(t--)
{
int n,k,i,j;
scanf("%d %d",&n,&k);
char s[n][n+1];
int ans[n],v[n],flag=0,q[n],start,end;
for(i=0;i<n;i++)
{
ans[i]=-1;
v[i]=0;
}
for(i=0;i<n;i++)
{
scanf("%s",s[i]);
}
int a[n][n];
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
a[i][j]=s[i][j]-'0';
}
}
ans[0]=0;
v[0]=1;
start=0;
q[start]=0;
end=1;
while(start<end)
{
i=q[start];
start++;
for(j=i-k;j<=i+k;j++)
{
if(j<0)
{
continue;
}
if(j==n)
{
break;
}
if(a[i][j]==1 && v[j]==0)
{
v[j]=1;
ans[j]=ans[i]+1;
q[end]=j;
end++;
}
}
}
printf("%d\n",ans[n-1]);
}
return 0;
}
Under the Tunnels CodeChef Solution in JAVA
“
import java.io.*;
import java.util.*;
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader()
{
br = new BufferedReader(
new InputStreamReader(System.in));
}
/* find distance of one postion wrt to another in circular arrray..
for(int i = 0; i< 2*n; i++)
time[(i+1)%n] = Math.min(time[(i+1)%n], time[i%n]+1); //checking with bacward position
for(int i = 2*n-1; i>= 0; i--)
time[(i+n-1)%n] = Math.min(time[(i+n-1)%n], time[i%n]+1);
*/
String next()
{
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
}
catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() { return Integer.parseInt(next()); }
long nextLong() { return Long.parseLong(next()); }
double nextDouble()
{
return Double.parseDouble(next());
}
String nextLine()
{
String str = "";
try {
str = br.readLine();
}
catch (IOException e) {
e.printStackTrace();
}
return str;
}
}
class Codechef {
static class pair implements Comparable<pair> {
int a;
int b;
pair(int x,int y){
a= x;
b= y;
}
public int compareTo(pair p) {
return b-p.b;
}
}
static boolean factors(int num){
for(int i=2;i*i<=num;i++) {
if(num%2==0) {
return false;
}
}
return true;
}
static long coPrimes(long n) {
long res = n;
for(int i=2;i*i<=n;i++) {
if(n%i==0) {
res = res/i;
res = res*(i-1);
while(n%i==0) {
n = n/i;
}
}
}
if(n!=1) {
res = res/n;
res = res*(n-1);
}
return res;
}
static long mod = 1000000007;
static void solve(FastReader sc, PrintWriter out) {
int n = sc.nextInt();
int k = sc.nextInt();
ArrayList<ArrayList<Integer>> al = new ArrayList<>();
for(int i=0;i<=n;i++) {
al.add(new ArrayList<Integer>());
}
for(int i=0;i<n;i++) {
String str = sc.nextLine();
for(int j=0;j<str.length();j++) {
if(str.charAt(j)=='1' && i!=j) {
al.get(i+1).add(j+1);
}
}
}
// System.out.println(al);
boolean vis[]= new boolean[n+1];
System.out.println(bfs(al,1,n,k,vis));
}
static int bfs(ArrayList<ArrayList<Integer>> graph,int src,int dest,int k,boolean vis[]) {
Queue<Integer> q = new ArrayDeque<>();
q.add(src);
int dist =0;
int flag = 0;
while(q.size()!=0) {
int size = q.size();
dist++;
while(size-->0) {
int rem = q.poll();
if(vis[rem]==true) {
continue;
}
if(rem==dest) {
flag= 1;
break;
}
vis[rem] = true;
for(int elem: graph.get(rem)) {
// System.out.println(elem+" ");
if(Math.abs(rem-elem)<=k ) {
q.add(elem);
//System.out.println("fejofjowfjwpokg");
}
}
}
if(flag == 1) {
break;
}
}
// System.out.println(dist);
if(flag==0) {
return -1;
}
return dist-1;
}
public static void main(String[] args) throws IOException{
FastReader sc = new FastReader();
PrintWriter out = new PrintWriter(System.out);
int t = sc.nextInt();
while(t-->0){
solve(sc,out);
}
out.close();
}
/*
static long rec(int n,int k,String arr[],int curr,boolean vis[],long dp[]) {
if(curr==n) {
//System.out.println(curr+" klfndj");
return 0;
}
if(curr<=0) {
return Integer.MAX_VALUE;
}
if(vis[curr]==true) {
return Integer.MAX_VALUE;
}
if(dp[curr]!=0) {
return dp[curr];
}
vis[curr]=true;
ArrayList<Integer> safePlace = new ArrayList<>();
String currStr = arr[curr-1];
for(int i=0;i<currStr.length();i++) {
if(currStr.charAt(i)=='1' && curr!=i+1) {
safePlace.add(i+1);
}
}
//System.out.println(curr+"-> "+safePlace);
if(safePlace.size()==0) {
return Integer.MAX_VALUE;
}
long moves= Long.MAX_VALUE;
for(int sPlace : safePlace) {
if(Math.abs(sPlace-curr)<=k) {
long recAns = rec(n,k,arr,curr+(sPlace-curr),vis,dp);
if(recAns!=Integer.MAX_VALUE) {
moves = Math.min(recAns+1, moves);
}
}
}
vis[curr]= false;
return dp[curr] = moves;
}
*/
}
//log10(number)+1 gives length of number. ex log10(123)+1 gives 3.
//Math.ceil(Math.log(x)/Math.log(2)) gives X which satisfy 2^X.Under the Tunnels CodeChef Solution in PYPY 3
“from collections import defaultdict
def calc(s,k,id):
r=[]
for i in range(max(id-k,0),min(id+k+1,len(s))):
if i==id:
continue
if s[i]=="1":
r.append(i)
return r
def f(q,k):
# print(q)
g=defaultdict(list)
for id,s in enumerate(q):
r=calc(s,k,id)
g[id]+=r
dis=[-1]*(len(q))
q=[0]
while q:
t=q.pop(0)
for i in g[t]:
if dis[i]==-1:
q.append(i)
dis[i]=dis[t]+1
if dis[-1]==-1:
return -1
else:
return dis[-1]+1
for _ in range(int(input())):
q=[]
n,k=map(int,input().strip().split())
for i in range(n):
q.append(input())
print(f(q,k))Under the Tunnels CodeChef Solution in PYTH
“t = int(raw_input())
for i in range(t):
st = raw_input().split()
N = int(st[0])
K = int(st[1])
ST = []
for k in range(N):
st = raw_input().strip()
ST.append(st)
# endfor k
STK = []
STK.append([0,0])
S = set()
S.add(0)
sz = 1
p = 0
T = N-1
done = False
while (p < sz) and (not done):
d = STK[p][0]
n = STK[p][1]
if (d+K >= T) and (ST[d][T] == '1'):
n += 1
done = True
else:
d1 = max(0,d-K)
d2 = min(T,d+K)
q = d2
while q >= d1:
if (ST[d][q] == '1') and (not q in S):
S.add(q)
STK.append([q,n+1])
sz += 1
# endif
q -= 1
# endwhile
# endif
p += 1
# endwhile
if not done:
n = -1
# endif
print n
# endfor i
Under the Tunnels CodeChef Solution in C#
“using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;
public class Test
{
public static void Main()
{
UnderTheTunnels.Run();
}
public class UnderTheTunnels
{
static char[][] staticMatrix;
static int[][] staticDistance;
public static void Run()
{
var T = Convert.ToInt32(Console.ReadLine());
var resul = new StringBuilder();
for (int t = 0; t < T; t++)
{
var NK = Array.ConvertAll(Console.ReadLine().Trim().Split(' '), int.Parse);
var N = NK[0];
var K = NK[1];
var matrix = new char[N][];
var distance = new int[N][];
for (int i = 0; i < N; i++)
{
matrix[i] = Console.ReadLine().Trim().ToCharArray();
distance[i] = new int[N];
}
staticMatrix = matrix;
staticDistance = distance;
travel(0, 0, K, N);
resul.AppendLine((staticDistance[N-1][N-1] == 0 ? -1 : staticDistance[N - 1][N - 1]) + "");
}
Console.WriteLine(resul.ToString().Trim());
}
static void travel(int row, int col, int k, int n)
{
//if (row == n - 1 && col == n - 1)
//{
// Console.WriteLine(staticDistance[row][col]);
//}
var index = 1;
while (index <= k && (col - index >= 0 || col + index < n))
{
if ((col - index != 0) && col - index >= 0 && staticMatrix[row][col - index] == '1' && (staticDistance[col - index][col - index] == 0 || staticDistance[col - index][col - index] > staticDistance[row][col] + 1))
{
staticDistance[col - index][col - index] = staticDistance[row][col] + 1;
travel(col - index, col - index, k, n);
}
if ((col + index != 0) && col + index < n && staticMatrix[row][col + index] == '1' && (staticDistance[col + index][col + index] == 0 || staticDistance[col + index][col + index] > staticDistance[row][col] + 1))
{
staticDistance[col + index][col + index] = staticDistance[row][col] + 1;
travel(col + index, col + index, k, n);
}
index++;
}
}
}
}Under the Tunnels CodeChef Solution in GO
“package main
import (
"bufio"
"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] != ' ' {
tmp = tmp*10 + int(bytes[i]-'0')
i++
}
*val = tmp * sign
return i
}
func readNum(scanner *bufio.Scanner) (a int) {
scanner.Scan()
readInt(scanner.Bytes(), 0, &a)
return
}
func readTwoNums(scanner *bufio.Scanner) (a int, b int) {
res := readNNums(scanner, 2)
a, b = res[0], res[1]
return
}
func readNNums(scanner *bufio.Scanner, n int) []int {
res := make([]int, n)
x := 0
scanner.Scan()
for i := 0; i < n; i++ {
for x < len(scanner.Bytes()) && scanner.Bytes()[x] == ' ' {
x++
}
x = readInt(scanner.Bytes(), x, &res[i])
}
return res
}
func fillNNums(scanner *bufio.Scanner, n int, res []int) {
x := 0
scanner.Scan()
for i := 0; i < n; i++ {
for x < len(scanner.Bytes()) && scanner.Bytes()[x] == ' ' {
x++
}
x = readInt(scanner.Bytes(), x, &res[i])
}
}
func readUint64(bytes []byte, from int, val *uint64) int {
i := from
var tmp uint64
for i < len(bytes) && bytes[i] != ' ' {
tmp = tmp*10 + uint64(bytes[i]-'0')
i++
}
*val = tmp
return i
}
func readInt64(bytes []byte, from int, val *int64) int {
i := from
var tmp int64
for i < len(bytes) && bytes[i] != ' ' {
tmp = tmp*10 + int64(bytes[i]-'0')
i++
}
*val = tmp
return i
}
func readNInt64Nums(scanner *bufio.Scanner, n int) []int64 {
res := make([]int64, n)
x := -1
scanner.Scan()
for i := 0; i < n; i++ {
x = readInt64(scanner.Bytes(), x+1, &res[i])
}
return res
}
func main() {
scanner := bufio.NewScanner(os.Stdin)
tc := readNum(scanner)
for tc > 0 {
tc--
n, K := readTwoNums(scanner)
S := make([]string, n)
for i := 0; i < n; i++ {
scanner.Scan()
S[i] = scanner.Text()
}
fmt.Println(solve(n, K, S))
}
}
func solve(n, K int, S []string) int {
if S[0][0] == '0' {
return -1
}
dist := make([]int, n)
for i := 0; i < n; i++ {
dist[i] = -1
}
dist[0] = 0
que := make([]int, n)
var front, end int
que[end] = 0
end++
for front < end {
u := que[front]
front++
x := max(0, u-K)
y := min(n-1, u+K)
for v := x; v <= y; v++ {
if S[u][v] == '1' && dist[v] < 0 {
dist[v] = dist[u] + 1
que[end] = v
end++
}
}
}
return dist[n-1]
}
func max(a, b int) int {
if a >= b {
return a
}
return b
}
func min(a, b int) int {
if a <= b {
return a
}
return b
}Under the Tunnels CodeChef Solution Review:
In our experience, we suggest you solve this Under the Tunnels 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 Under the Tunnels CodeChef Solution.
“Conclusion:
I hope this Under the Tunnels 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!
