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 |
|
|
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 |