Submission #3414562


Source Code Expand

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

var sc = bufio.NewScanner(os.Stdin)

// NextLine reads a line text from stdin, and then returns its string.
func NextLine() string {
	sc.Scan()
	return sc.Text()
}

// NextIntsLine reads a line text, that consists of **ONLY INTEGERS DELIMITED BY SPACES**, from stdin.
// And then returns intergers slice.
func NextIntsLine() []int {
	ints := []int{}
	intsStr := NextLine()
	tmp := strings.Split(intsStr, " ")
	for _, s := range tmp {
		integer, _ := strconv.Atoi(s)
		ints = append(ints, integer)
	}
	return ints
}

// NextRunesLine reads a line text, that consists of **ONLY CHARACTERS ARRANGED CONTINUOUSLY**, from stdin.
// Ant then returns runes slice.
func NextRunesLine() []rune {
	return []rune(NextLine())
}

var r, c, sy, sx, gy, gx int
var C [][]rune
var memo [100][100]int

const INF = 1000000

type next [3]int

var delta [4][2]int

func main() {
	tmp := NextIntsLine()
	r, c = tmp[0], tmp[1]
	tmp = NextIntsLine()
	sy, sx = tmp[0]-1, tmp[1]-1
	tmp = NextIntsLine()
	gy, gx = tmp[0]-1, tmp[1]-1
	for i := 0; i < r; i++ {
		row := NextRunesLine()
		C = append(C, row)
	}

	for i := 0; i < r; i++ {
		for j := 0; j < c; j++ {
			memo[i][j] = INF
		}
	}

	delta = [4][2]int{
		[2]int{0, 1},
		[2]int{1, 0},
		[2]int{0, -1},
		[2]int{-1, 0},
	}

	queue := []next{}
	queue = append(queue, next{sx, sy, 0})
	for len(queue) > 0 {
		now := queue[0]
		queue = queue[1:]
		nx, ny := now[0], now[1]
		memo[ny][nx] = now[2]
		if nx == gx && ny == gy {
			break
		}

		for _, d := range delta {
			dy, dx := ny+d[0], nx+d[1]
			if memo[dy][dx] == INF && C[dy][dx] == '.' {
				queue = append(queue, next{dx, dy, now[2] + 1})
			}
		}
	}

	fmt.Println(memo[gy][gx])
}

Submission Info

Submission Time
Task C - 幅優先探索
User maguroguma
Language Go (1.6)
Score 0
Code Size 1829 Byte
Status TLE
Exec Time 2114 ms
Memory 1773952 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 2
TLE × 1
AC × 13
TLE × 11
MLE × 1
Set Name Test Cases
Sample subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt
All subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt
Case Name Status Exec Time Memory
subtask0_sample01.txt AC 1 ms 640 KB
subtask0_sample02.txt AC 1 ms 640 KB
subtask0_sample03.txt TLE 2113 ms 1505408 KB
subtask1_01.txt AC 1 ms 768 KB
subtask1_02.txt AC 1 ms 768 KB
subtask1_03.txt AC 1 ms 768 KB
subtask1_04.txt TLE 2114 ms 1773952 KB
subtask1_05.txt TLE 2113 ms 1550464 KB
subtask1_06.txt TLE 2112 ms 956032 KB
subtask1_07.txt AC 1 ms 640 KB
subtask1_08.txt AC 1 ms 640 KB
subtask1_09.txt TLE 2111 ms 774400 KB
subtask1_10.txt AC 2 ms 1408 KB
subtask1_11.txt TLE 2112 ms 1337216 KB
subtask1_12.txt TLE 2112 ms 1347328 KB
subtask1_13.txt AC 219 ms 32256 KB
subtask1_14.txt AC 1 ms 640 KB
subtask1_15.txt TLE 2110 ms 427648 KB
subtask1_16.txt MLE 1901 ms 345216 KB
subtask1_17.txt TLE 2111 ms 1035776 KB
subtask1_18.txt TLE 2111 ms 695936 KB
subtask1_19.txt AC 1 ms 896 KB
subtask1_20.txt AC 2 ms 1152 KB
subtask1_21.txt TLE 2112 ms 1169024 KB
subtask1_22.txt AC 9 ms 6528 KB