Submission #420569

---

Source Code Expand

import java.io.BufferedReader;
import java.io.File;
import java.io.IOException;
import java.io.InputStreamReader;
import java.net.URL;
import java.util.ArrayList;
import java.util.Enumeration;
import java.util.List;
import java.util.Scanner;

public class Main {
    private static final String TAG = Main.class.getSimpleName();
    private static final BufferedReader br = new BufferedReader(
            new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        Integer hw[] = nextInts();
        char[][] m = new char[hw[0]][hw[1]];

        boolean ss = false;
        boolean gg = false;
        int[] s = new int[2];
        int[] g = new int[2];

        for (int i = 0; i < hw[0]; i++) {
            // for (int j = 0; j < hw[1]; j++) {
            // String line = nextLine();
            // line.split(" ");
            // }
            String line = nextLine();
            m[i] = line.toCharArray();

            if (!ss) {
                int k = line.indexOf("s");

                if (k >= 0) {
                    s[0] = i;
                    s[1] = k;
                    ss = true;
                }
            }

            if (!gg) {
                int k = line.indexOf("g");

                if (k >= 0) {
                    g[0] = i;
                    g[1] = k;
                    gg = true;
                }
            }
        }

        ans(a(m.clone(), s[0], s[1]) ? "YES" : "NO");
    }

    private static boolean a(char[][] m, int start, int end) {
        if (go(m, start + 1, end)) {
            m[start][end] = '#';
            if (correct(m, start + 1, end)) {
                return true;
            }

            if (a(m.clone(), start + 1, end)) {
                return true;
            }
        }

        if (go(m, start, end + 1)) {
            m[start][end] = '#';
            if (correct(m, start, end + 1)) {
                return true;
            }

            if (a(m.clone(), start, end + 1)) {
                return true;
            }
        }

        if (go(m, start - 1, end)) {
            m[start][end] = '#';
            if (correct(m, start - 1, end)) {
                return true;
            }
            if (a(m.clone(), start - 1, end)) {
                return true;
            }
        }

        if (go(m, start, end - 1)) {
            m[start][end] = '#';
            if (correct(m, start, end - 1)) {
                return true;
            }
            if (a(m.clone(), start, end - 1)) {
                return true;
            }
        }

        return false;
    }

    private static boolean go(char[][] m, int start, int end) {
        if (start < 0 || end < 0 || m.length <= start || m[0].length <= end) {
            return false;
        }

        if (m[start][end] == '#') {
            return false;
        } else {
            return true;
        }
    }

    private static boolean correct(char[][] m, int start, int end) {
        if (m[start][end] == 'g') {
            return true;
        } else {
            return false;
        }
    }

    private static String nextLine() throws IOException {
        return br.readLine();
    }

    private static Integer nextInt() throws NumberFormatException, IOException {
        return Integer.parseInt(br.readLine());
    }

    private static String[] nextLines() throws IOException {
        return br.readLine().split(" ");
    }

    private static Integer[] nextInts() throws IOException {
        String[] s = nextLines();
        Integer[] ints = new Integer[s.length];
        for (int i = 0; i < ints.length; i++) {
            ints[i] = Integer.parseInt(s[i]);
        }
        return ints;
    }

    private static void ans(Object s) {
        System.out.println(s.toString());
    }
}

Submission Info

Judge Result