CSES - Putka Open 2015 – 4/6

Submission details
Task:	Labyrintti
Sender:
Submission time:	2015-10-09 23:57:39 +0300
Language:	Java
Status:	READY
Result:	12

Feedback
group	verdict	score
#1	ACCEPTED	12
#2	TIME LIMIT EXCEEDED	0
#3	RUNTIME ERROR	0

Test results
test	verdict	time	group
#1	ACCEPTED	0.20 s	1	details
#2	ACCEPTED	0.19 s	1	details
#3	ACCEPTED	0.20 s	1	details
#4	ACCEPTED	0.20 s	1	details
#5	ACCEPTED	0.20 s	1	details
#6	ACCEPTED	0.72 s	2	details
#7	TIME LIMIT EXCEEDED	--	2	details
#8	TIME LIMIT EXCEEDED	--	2	details
#9	TIME LIMIT EXCEEDED	--	2	details
#10	ACCEPTED	0.64 s	2	details
#11	RUNTIME ERROR	0.19 s	3	details
#12	RUNTIME ERROR	0.18 s	3	details
#13	RUNTIME ERROR	0.20 s	3	details
#14	RUNTIME ERROR	0.20 s	3	details
#15	RUNTIME ERROR	0.20 s	3	details

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<10000; 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` view save

correct output
`3` view save

user output
`3` view save

Test 2

Group: 1

Verdict: ACCEPTED

input
`-8 2 8 -9` view save

correct output
`27` view save

user output
`27` view save

Test 3

Group: 1

Verdict: ACCEPTED

input
`3 2 -5 -1` view save

correct output
`13` view save

user output
`13` view save

Test 4

Group: 1

Verdict: ACCEPTED

input
`4 4 2 7` view save

correct output
`5` view save

user output
`5` view save

Test 5

Group: 1

Verdict: ACCEPTED

input
`-5 4 -6 -3` view save

correct output
`8` view save

user output
`8` view save

Test 6

Group: 2

Verdict: ACCEPTED

input
`-156 226 -9 7` view save

correct output
`438` view save

user output
`438` view save

Test 7

Group: 2

Verdict: TIME LIMIT EXCEEDED

input
`403 265 10 0` view save

correct output
`1100` view save

user output
(empty)

Test 8

Group: 2

Verdict: TIME LIMIT EXCEEDED

input
`146 462 9 -3` view save

correct output
`1160` view save

user output
(empty)

Test 9

Group: 2

Verdict: TIME LIMIT EXCEEDED

input
`223 82 -1 5` view save

correct output
`725` view save

user output
(empty)

Test 10

Group: 2

Verdict: ACCEPTED

input
`1 390 -5 2` view save

correct output
`436` view save

user output
`436` view save

Test 11

Group: 3

Verdict: RUNTIME ERROR

input
`-540305713988379 -580514137141...` view save

correct output
`1233409841814111` view save

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: RUNTIME ERROR

input
`-156703691254895 -816797859965...` view save

correct output
`1086091541904259` view save

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: RUNTIME ERROR

input
`-438806811971369 -748477242640...` view save

correct output
`1299874045296142` view save

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: RUNTIME ERROR

input
`939351840049839 -9541207461566...` view save

correct output
`2118652567575152` view save

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: RUNTIME ERROR

input
`-840127817790022 1113515308437...` view save

correct output
`1007774343975947` view save

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)

Putka Open 2015 – 4/6

Labyrintti

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Tasks

Submissions ()