Submission #420856

---

Source Code Expand

import java.util.*;
import java.io.*;
import static java.util.Arrays.*;
import static java.lang.Math.*;

public class Main {
    
    static final Scanner in = new Scanner(System.in);
    static final PrintWriter out = new PrintWriter(System.out,false);

    static void solve() {
        int h = in.nextInt();
        int w = in.nextInt();
        UnionFind uf = new UnionFind(h*w);
     	char[][] c = new char[h][w];
     	int[] dy = {0,1,0,-1};
   		int[] dx = {1,0,-1,0};
   		int s=-1,g=-1;

        for (int i=0; i<h; i++) {
        	c[i] = in.next().toCharArray();
        	for (int j=0; j<w; j++) {
        		if (c[i][j] == 's') {
        			s = i*w+j;
        		}else if (c[i][j] == 'g') {
        			g = i*w+j;
        		}else if (c[i][j] == '.' || c[i][j] == 's' || c[i][j] == 'g') {
        			for (int k=0; k<4; k++) {
        				int y = i + dy[k];
    					int x = j + dx[k];
    					if (y < 0 || h <= y || x < 0 || w <= x) continue;
    					if (c[y][x] == '.' || c[y][x] == 's' || c[y][x] == 'g') uf.unite(i*w+j,y*w+x);
        			}
        		}
        	}
        }
        
        out.println(uf.same(s,g)?"Yes":"No");
    }

    static class UnionFind {
    
    	int[] node;
    
    	public UnionFind(int n){
    		node = new int[n];
    		for (int i=0; i<n; i++)
    			node[i] = i;
    	}
    
    	int find(int x){
    		if(node[x] == x)
    			return x;
    		return node[x] = find(node[x]);
    	}
    
    	boolean same(int x,int y){
    		return find(x) == find(y);
    	}
    
    	void unite(int x,int y){
    		if (find(x) == find(y))
    			return;
    		node[find(x)] = find(y);
    	}
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();

        solve();
        out.flush();

        long end = System.currentTimeMillis();
        //trace(end-start + "ms");
        in.close();
        out.close();
    }

    static void trace(Object... o) { System.out.println(Arrays.deepToString(o));}
}

Submission Info

Judge Result