Submission #2558264


Source Code Expand

import Control.Applicative
import Control.Monad
import Data.Array.IO
import Data.Array.Unboxed
import Data.List
import Data.Maybe
import qualified Data.ByteString.Char8 as B
import Debug.Trace
import System.IO

type Point = (Int,Int)
type IOField = IOUArray Point Char

canmove :: (Int,Int) -> IOField -> (Int,Int) -> IO Bool
canmove (h,w) fld (i,j)
    | (i<0 || i>=h || j<0 || j>=w) = return False
    | otherwise = do
        c <- readArray fld (i,j)
        case c of
            '.' -> return True
            'g' -> return True
            otherwise -> return False

solve:: (IOField -> (Int,Int) -> IO Bool) -> IOField -> (Int,Int) -> IO String
solve f fld p@(i,j) = do
    c <- readArray fld p
    case c of
        'g' -> return "Yes"
        otherwise -> do
            writeArray fld p 'x'
            mv <- filterM (f fld) [(i-1,j),(i,j-1),(i+1,j),(i,j+1)]
            chk mv
    where chk [] = return "No"
          chk (m:ms) = do
            rs <- solve f fld m
            case rs of
                "Yes" -> return "Yes"
                otherwise -> chk ms

main = do
    [h,w] <- map read.words <$> getLine
    fld   <- newArray ((0,0),(h-1,w-1)) '.' :: IO IOField
    (sp:_) <- (concat <$>) $ forM [0..h-1] $ \i -> do
                ls <- B.getLine
                (concat <$>) $ forM [0..w-1] $ \j -> do
                    let c = B.index ls j
                    writeArray fld (i,j) c
                    case c of
                        's' -> return [(i,j)]
                        otherwise -> return []
    putStrLn =<< solve (canmove (h,w)) fld sp

Submission Info

Submission Time
Task A - 深さ優先探索
User mick0321
Language Haskell (GHC 7.10.3)
Score 100
Code Size 1629 Byte
Status AC
Exec Time 191 ms
Memory 61564 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 5
AC × 83
Set Name Test Cases
Sample 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 00_sample_05.txt
All 00_min_01.txt, 00_min_02.txt, 00_min_03.txt, 00_min_04.txt, 00_min_05.txt, 00_min_06.txt, 00_min_07.txt, 00_min_08.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 00_sample_05.txt, 01_rnd_00.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 01_rnd_10.txt, 01_rnd_11.txt, 01_rnd_12.txt, 01_rnd_13.txt, 01_rnd_14.txt, 01_rnd_15.txt, 01_rnd_16.txt, 01_rnd_17.txt, 01_rnd_18.txt, 01_rnd_19.txt, 02_rndhard_00.txt, 02_rndhard_01.txt, 02_rndhard_02.txt, 02_rndhard_03.txt, 02_rndhard_04.txt, 02_rndhard_05.txt, 02_rndhard_06.txt, 02_rndhard_07.txt, 02_rndhard_08.txt, 02_rndhard_09.txt, 02_rndhard_10.txt, 02_rndhard_11.txt, 02_rndhard_12.txt, 02_rndhard_13.txt, 02_rndhard_14.txt, 02_rndhard_15.txt, 02_rndhard_16.txt, 02_rndhard_17.txt, 02_rndhard_18.txt, 02_rndhard_19.txt, 02_rndhard_20.txt, 02_rndhard_21.txt, 02_rndhard_22.txt, 02_rndhard_23.txt, 02_rndhard_24.txt, 02_rndhard_25.txt, 02_rndhard_26.txt, 02_rndhard_27.txt, 02_rndhard_28.txt, 02_rndhard_29.txt, 02_rndhard_30.txt, 02_rndhard_31.txt, 02_rndhard_32.txt, 02_rndhard_33.txt, 02_rndhard_34.txt, 02_rndhard_35.txt, 02_rndhard_36.txt, 02_rndhard_37.txt, 02_rndhard_38.txt, 02_rndhard_39.txt, 03_rndhardsmall_00.txt, 03_rndhardsmall_01.txt, 03_rndhardsmall_02.txt, 03_rndhardsmall_03.txt, 03_rndhardsmall_04.txt, 03_rndhardsmall_05.txt, 03_rndhardsmall_06.txt, 03_rndhardsmall_07.txt, 03_rndhardsmall_08.txt, 03_rndhardsmall_09.txt
Case Name Status Exec Time Memory
00_min_01.txt AC 2 ms 508 KB
00_min_02.txt AC 2 ms 508 KB
00_min_03.txt AC 2 ms 508 KB
00_min_04.txt AC 2 ms 508 KB
00_min_05.txt AC 2 ms 508 KB
00_min_06.txt AC 2 ms 508 KB
00_min_07.txt AC 2 ms 508 KB
00_min_08.txt AC 2 ms 508 KB
00_sample_01.txt AC 2 ms 508 KB
00_sample_02.txt AC 2 ms 508 KB
00_sample_03.txt AC 2 ms 508 KB
00_sample_04.txt AC 2 ms 508 KB
00_sample_05.txt AC 2 ms 508 KB
01_rnd_00.txt AC 26 ms 13308 KB
01_rnd_01.txt AC 147 ms 52476 KB
01_rnd_02.txt AC 69 ms 18428 KB
01_rnd_03.txt AC 149 ms 50556 KB
01_rnd_04.txt AC 191 ms 61564 KB
01_rnd_05.txt AC 18 ms 8572 KB
01_rnd_06.txt AC 59 ms 17276 KB
01_rnd_07.txt AC 66 ms 16764 KB
01_rnd_08.txt AC 23 ms 12796 KB
01_rnd_09.txt AC 25 ms 13308 KB
01_rnd_10.txt AC 59 ms 13692 KB
01_rnd_11.txt AC 25 ms 13308 KB
01_rnd_12.txt AC 156 ms 50812 KB
01_rnd_13.txt AC 146 ms 41724 KB
01_rnd_14.txt AC 24 ms 13308 KB
01_rnd_15.txt AC 25 ms 13436 KB
01_rnd_16.txt AC 26 ms 13308 KB
01_rnd_17.txt AC 72 ms 13692 KB
01_rnd_18.txt AC 25 ms 13308 KB
01_rnd_19.txt AC 27 ms 13308 KB
02_rndhard_00.txt AC 26 ms 13308 KB
02_rndhard_01.txt AC 26 ms 13308 KB
02_rndhard_02.txt AC 26 ms 8572 KB
02_rndhard_03.txt AC 25 ms 8572 KB
02_rndhard_04.txt AC 25 ms 13308 KB
02_rndhard_05.txt AC 25 ms 13308 KB
02_rndhard_06.txt AC 25 ms 13308 KB
02_rndhard_07.txt AC 25 ms 13308 KB
02_rndhard_08.txt AC 26 ms 13436 KB
02_rndhard_09.txt AC 26 ms 13308 KB
02_rndhard_10.txt AC 19 ms 8572 KB
02_rndhard_11.txt AC 19 ms 8572 KB
02_rndhard_12.txt AC 25 ms 13308 KB
02_rndhard_13.txt AC 25 ms 13436 KB
02_rndhard_14.txt AC 27 ms 13436 KB
02_rndhard_15.txt AC 27 ms 13308 KB
02_rndhard_16.txt AC 18 ms 8444 KB
02_rndhard_17.txt AC 18 ms 8444 KB
02_rndhard_18.txt AC 25 ms 13308 KB
02_rndhard_19.txt AC 24 ms 13308 KB
02_rndhard_20.txt AC 18 ms 8572 KB
02_rndhard_21.txt AC 17 ms 8572 KB
02_rndhard_22.txt AC 25 ms 13436 KB
02_rndhard_23.txt AC 26 ms 13436 KB
02_rndhard_24.txt AC 25 ms 13308 KB
02_rndhard_25.txt AC 25 ms 13308 KB
02_rndhard_26.txt AC 23 ms 12796 KB
02_rndhard_27.txt AC 23 ms 12796 KB
02_rndhard_28.txt AC 25 ms 13436 KB
02_rndhard_29.txt AC 25 ms 13308 KB
02_rndhard_30.txt AC 24 ms 13308 KB
02_rndhard_31.txt AC 24 ms 13308 KB
02_rndhard_32.txt AC 25 ms 13308 KB
02_rndhard_33.txt AC 25 ms 13436 KB
02_rndhard_34.txt AC 25 ms 13308 KB
02_rndhard_35.txt AC 26 ms 13308 KB
02_rndhard_36.txt AC 25 ms 13308 KB
02_rndhard_37.txt AC 25 ms 13308 KB
02_rndhard_38.txt AC 24 ms 13436 KB
02_rndhard_39.txt AC 24 ms 13436 KB
03_rndhardsmall_00.txt AC 1 ms 508 KB
03_rndhardsmall_01.txt AC 1 ms 508 KB
03_rndhardsmall_02.txt AC 1 ms 508 KB
03_rndhardsmall_03.txt AC 1 ms 508 KB
03_rndhardsmall_04.txt AC 1 ms 508 KB
03_rndhardsmall_05.txt AC 1 ms 508 KB
03_rndhardsmall_06.txt AC 1 ms 508 KB
03_rndhardsmall_07.txt AC 1 ms 508 KB
03_rndhardsmall_08.txt AC 1 ms 508 KB
03_rndhardsmall_09.txt AC 1 ms 508 KB