Saturday, May 29, 2021

codeforces 43D Solution D.Journey (codeforces 43D) (rank 2000*)

43D. Journey

Problem Link: "https://codeforces.com/problemset/problem/43/D"


Solution 1:
import java.util.*;

public class traveseKing {
    public static Scanner scn = new Scanner(System.in);
 
    public static int counter = 0;
 
    public static boolean isTelepoter(int[][] arrint iint jint nint mint countArrayList<int[]> al,
            int[][] dirEvenint[][] dirOdd) {
        if (n == 1 && m == 1) {
            System.out.println(0 + "\n" + 1 + "\t" + 1);
            return true;
        }
        if (count >= n * m - 1 && ((i == 1 && j == 2) || (i == 2 && j == 1))) {
            System.out.println(0 + "\n" + 1 + "\t" + 1);
            for (int x = 0x < al.size(); x++) {
                for (int y = 0y < 2y++) {
                    System.out.print(al.get(x)[y] + "\t");
                }
                System.out.println();
            }
            System.out.println(1 + "\t" + 1);
 
            return true;
        }
 
        if (count >= n * m - 1)
            counter = count + 1;
        if (counter >= n * m)
            return false;
        boolean recAns = false;
 
        for (int x = 0x < dirEven.lengthx++) {
            int newi = 0newj = 0;
            if (m % 2 == 0) {
                newi = i + dirEven[x][0];
                newj = j + dirEven[x][1];
            } else {
                newi = i + dirOdd[x][0];
                newj = j + dirOdd[x][1];
            }
            if ((newi <= n && newi >= 1) && (newj <= m && newj >= 1) && arr[newi - 1][newj - 1] < 1) {
                al.add(new int[] { newi,newj });
                arr[newi - 1][newj - 1]++;
                recAns = isTelepoter(arrnewinewjnmcount + 1aldirEvendirOdd);
                al.remove(al.size() - 1);
                arr[newi - 1][newj - 1]--;
            }
            if (recAns)
                return true;
        }
        return recAns;
 
    }
 
    public static void traverse(int[][] arrint iint jint nint mArrayList<int[]> al) {
        boolean isTele = true;
        int[][] dirOdd = { { 01 }, { 10 }, { 0, -1 }, { -10 } };
        int[][] dirEven = { { 01 }, { 10 }, { -10 }, { 0, -1 } };
        isTele = isTelepoter(arr11nm0aldirEvendirOdd);
 
        if (!isTele) {
            System.out.println(1);
            if (n % 2 == 1)
                System.out.println(n + "\t" + m + "\t" + 1 + "\t" + 1);
            else
                System.out.println(n + "\t" + 1 + "\t" + 1 + "\t" + 1);
 
            for (int x = 0x < nx++) {
                if (x % 2 == 0)
                    for (int y = 0y < my++) {
                        System.out.println((x + 1) + "\t" + (y + 1));
                    }
                else
                    for (int y = m - 1y >= 0y--) {
                        System.out.println((x + 1) + "\t" + (y + 1));
 
                    }
            }
            System.out.println(1 + "\t" + 1);
 
        }
 
    }
 
    public static void main(String[] argv) {
        int n = scn.nextInt();
        int m = scn.nextInt();
        ArrayList<int[]> al = new ArrayList<>();
        int[][] arr = new int[n][m];
        traverse(arr11nmal);
    }
}




Solution 2: Better than First:


import java.util.*;

public class traveseKing {

    public static Scanner scn = new Scanner(System.in);

    public static int counter = 0;

    public static boolean isTelepoter(int[][] arrint iint jint nint mint countArrayList<int[]> al,
            int[][] dir) {
        if (n == 1 && m == 1) {
            System.out.println(0 + "\n" + 1 + "\t" + 1);
            return true;
        }
        if (count >= n * m - 1 && ((i == 1 && j == 2) || (i == 2 && j == 1))) {
            System.out.println(0 + "\n" + 1 + "\t" + 1);
            for (int x = 0x < al.size(); x++) {
                for (int y = 0y < 2y++) {
                    System.out.print(al.get(x)[y] + "\t");
                }
                System.out.println();
            }
            System.out.println(1 + "\t" + 1);

            return true;
        }
        if (count >= n * m - 1)
            counter = count + 1;
        if (counter >= n * m)
            return false;

        boolean recAns = false;

        for (int x = 0x < dir.lengthx++) {
            int newi = 0newj = 0;

            newi = i + dir[x][0];
            newj = j + dir[x][1];

            if ((newi <= n && newi >= 1) && (newj <= m && newj >= 1) && arr[newi - 1][newj - 1] < 1) {
                al.add(new int[] { newinewj });
                arr[newi - 1][newj - 1]++;
                recAns = isTelepoter(arrnewinewjnmcount + 1aldir);
                al.remove(al.size() - 1);
                arr[newi - 1][newj - 1]--;
            }
            if (recAns)
                return true;
        }
        return recAns;

    }

    public static void traverse(int[][] arrint iint jint nint mArrayList<int[]> al) {
        boolean istelefalse;
        int[][] dirOdd = { { 01 }, { 10 }, { 0, -1 }, { -10 } };
        int[][] dirEven = { { 01 }, { 10 }, { -10 }, { 0, -1 } };

         if (m % 2 == 1 && !(n % 2 == 1 && m % 2 == 1))
            istele = isTelepoter(arr11nm0aldirOdd);
        if(m%2==0 && !(n % 2 == 1 && m % 2 == 1)) 
            istele = isTelepoter(arr11nm0aldirEven);
        if (!istele) {
            System.out.println(1);
            if (n % 2 == 1)
                System.out.println(n + "\t" + m + "\t" + 1 + "\t" + 1);
            else
                System.out.println(n + "\t" + 1 + "\t" + 1 + "\t" + 1);

            for (int x = 0x < nx++) {
                if (x % 2 == 0)
                    for (int y = 0y < my++) {
                        System.out.println((x + 1) + "\t" + (y + 1));
                    }
                else
                    for (int y = m - 1y >= 0y--) {
                        System.out.println((x + 1) + "\t" + (y + 1));

                    }
            }
            System.out.println(1 + "\t" + 1);

        } 

    }

    public static void main(String[] argv) {
        int n = scn.nextInt();
        int m = scn.nextInt();
        ArrayList<int[]> al = new ArrayList<>();
        int[][] arr = new int[n][m];
        traverse(arr11nmal);
    }

}

No comments:

Post a Comment

Thanks

Climate Crisis and Innovation: Navigating Earth's Future

Climate Change: Recent Events and Technological Solutions 1. The Escalating Climate Crisis The climate crisis has intensified in recent year...