[LIVE] 식당예제 <Java>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class B2_RestaurantTest {
	static int R,C,cnt=0;
	static char[][] map;
	static boolean[][] visited;
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		map = new char[R][];
		visited = new boolean[R][C];
		
		for(int i=0;i<R;i++) {
			map[i] = in.readLine().toCharArray();
		}
		makePipe();
		System.out.println(cnt);
	}
	
	private static void makePipe() {
		cnt=0;
		//윗줄부터 시도
		for(int i=0;i<R;i++) {
			visited[i][0] = true;
			dfs(i,0);
			
		}
	
	
	}
	static int[] dr = {-1,0,1};
	private static boolean dfs(int r, int c) {//현재 탐색위치 받아야함
		if(c==C-1) {
			cnt++;
			return true;//파이프놓기 성공
		}
		
		int nr, nc = c+1;
		for(int d=0;d<3;d++) {
			nr = r+dr[d];
			if(nr<0 || nr>=R || map[nr][nc]=='x' ||visited[nr][nc]) continue;//열은 기저조건에서 제한(경계체크x)
				visited[nr][nc]=true;
				if(dfs(nr,nc)) return true;//끝까지 갔다 왔으면 계속 리턴
				//visited[nr][nc]=false; //실패했던 흔적 되돌리지 않기 : 뒤의 선택지의 방향은 현재보다 유리하지 않은 상황이고 결국 같은 상황이다.
		}
		
		return false;//파이프놓기 실패
	}
	
	
}