CSES - Putka Open 2015 – 4/6 - Results
Submission details
Task:Labyrintti
Sender:
Submission time:2015-10-10 00:01:47 +0300
Language:Java
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.44 s1details
#2ACCEPTED0.46 s1details
#3ACCEPTED0.45 s1details
#4--1details
#5ACCEPTED0.45 s1details
#6--2details
#7--2details
#8--2details
#9--2details
#10--2details
#110.47 s3details
#120.45 s3details
#130.46 s3details
#140.44 s3details
#150.45 s3details

Code

//package labyrintti;

import java.util.ArrayDeque;
import java.util.HashSet;

/**
 *
 * @author Adreno
 */
public class Labyrintti {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        IO io = new IO();
        HashSet<Ruutu> seinat = new HashSet<>();
        int y=0;
        int x=0;
        int count = 2;
        long kaannos = 2;
        long kaannokseen = 0;
        int suunta = 0;
        for (int i=0; i<1000000; i++) {
            //System.out.println("Seinä y=" + y + ", x=" +x + ", kaannokseen=" + kaannokseen + ", kaannos=" + kaannos);
            seinat.add(new Ruutu(y,x,0));
            kaannokseen++;
            if      (suunta == 0) x++;
            else if (suunta == 1) y--;
            else if (suunta == 2) x--;
            else                  y++;
            if (kaannokseen == kaannos) {
                kaannos = (long) Math.pow(2, count);
                count++;
                kaannokseen = 0;
                suunta++;
                suunta %= 4;
            }
        }
        
        //piirraKartta(20, seinat);
        
        Ruutu alku = new Ruutu(io.nextInt(), io.nextInt(), 0);
        Ruutu loppu = new Ruutu(io.nextInt(), io.nextInt(), 0);
        System.out.println(lyhinReitti(alku, loppu, seinat));
        
        io.close();
    }
    
    public static void piirraKartta(int n, HashSet<Ruutu> seinat) {
        for (int y=-n; y<=n; y++) {
            for (int x=-n; x<=n; x++) {
                System.out.print(seinat.contains(new Ruutu(y,x,0)) ? "#" : ".");
            }
            System.out.println("");
        }
    }
    
    public static int lyhinReitti(Ruutu alku, Ruutu loppu, HashSet<Ruutu> seinat) {
        ArrayDeque<Ruutu> jono = new ArrayDeque<>();
        jono.add(alku);
        while (!jono.isEmpty()) {
            Ruutu nyk = jono.pollFirst();
            if (!seinat.add(nyk)) continue;
            //System.out.println("Tutkitaan ruutua " + nyk.toString());
            if (nyk.equals(loppu)) return nyk.steps;
            jono.addLast(new Ruutu(nyk.y + 1, nyk.x, nyk.steps+1));
            jono.addLast(new Ruutu(nyk.y - 1, nyk.x, nyk.steps+1));
            jono.addLast(new Ruutu(nyk.y, nyk.x + 1, nyk.steps+1));
            jono.addLast(new Ruutu(nyk.y, nyk.x - 1, nyk.steps+1));
        }
        return -1;
    }
    
}

class Ruutu {
    public int y;
    public int x;
    public int steps;

    public Ruutu(int y, int x, int steps) {
        this.y = y;
        this.x = x;
        this.steps = steps;
    }

    @Override
    public boolean equals(Object obj) {
        Ruutu toinen = (Ruutu) obj;
        return (this.x == toinen.x && this.y == toinen.y);
    }

    @Override
    public int hashCode() {
        return this.y*36 + this.x;
    }
    
    

    @Override
    public String toString() {
        return "y=" + y + ", x=" + x + ", steps=" + steps;
    }
    
    
    
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
6 -1 8 -2

correct output
3

user output
3

Test 2

Group: 1

Verdict: ACCEPTED

input
-8 2 8 -9

correct output
27

user output
27

Test 3

Group: 1

Verdict: ACCEPTED

input
3 2 -5 -1

correct output
13

user output
13

Test 4

Group: 1

Verdict:

input
4 4 2 7

correct output
5

user output
(empty)

Test 5

Group: 1

Verdict: ACCEPTED

input
-5 4 -6 -3

correct output
8

user output
8

Test 6

Group: 2

Verdict:

input
-156 226 -9 7

correct output
438

user output
(empty)

Test 7

Group: 2

Verdict:

input
403 265 10 0

correct output
1100

user output
(empty)

Test 8

Group: 2

Verdict:

input
146 462 9 -3

correct output
1160

user output
(empty)

Test 9

Group: 2

Verdict:

input
223 82 -1 5

correct output
725

user output
(empty)

Test 10

Group: 2

Verdict:

input
1 390 -5 2

correct output
436

user output
(empty)

Test 11

Group: 3

Verdict:

input
-540305713988379 -580514137141...

correct output
1233409841814111

user output
(empty)

Error:
Exception in thread "main" java.lang.RuntimeException: IO.nextInt: Invalid int.
	at IO.nextInt(IO.java:106)
	at Labyrintti.main(Labyrintti.java:44)

Test 12

Group: 3

Verdict:

input
-156703691254895 -816797859965...

correct output
1086091541904259

user output
(empty)

Error:
Exception in thread "main" java.lang.RuntimeException: IO.nextInt: Invalid int.
	at IO.nextInt(IO.java:106)
	at Labyrintti.main(Labyrintti.java:44)

Test 13

Group: 3

Verdict:

input
-438806811971369 -748477242640...

correct output
1299874045296142

user output
(empty)

Error:
Exception in thread "main" java.lang.RuntimeException: IO.nextInt: Invalid int.
	at IO.nextInt(IO.java:106)
	at Labyrintti.main(Labyrintti.java:44)

Test 14

Group: 3

Verdict:

input
939351840049839 -9541207461566...

correct output
2118652567575152

user output
(empty)

Error:
Exception in thread "main" java.lang.RuntimeException: IO.nextInt: Invalid int.
	at IO.nextInt(IO.java:106)
	at Labyrintti.main(Labyrintti.java:44)

Test 15

Group: 3

Verdict:

input
-840127817790022 1113515308437...

correct output
1007774343975947

user output
(empty)

Error:
Exception in thread "main" java.lang.RuntimeException: IO.nextInt: Invalid int.
	at IO.nextInt(IO.java:106)
	at Labyrintti.main(Labyrintti.java:44)