白俊-319:パン屋[ジャワ]

import java.util.*;
import java.io.*;

public class Main {
	// 첫째 열 : 근처 빵집의 가스관
	// 마지막 열 : 원웅이의 빵집
	// 가스관과 빵집 연결하는 파이프 설치
	// 각 칸은 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선으로 연결 가능
	// 건물 : x, 빈칸 : .
	// 가스관과 빵집을 연결하는 파이프라인의 최대 개수 구하기
	static int R, C, result;
	static char[][] map;
	static int[] dr = { -1, 0, 1 };
	static int[] dc = { 1, 1, 1 };
	static boolean[][] isSelected;
	static boolean check;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());

		map = new char[R][C];
		for (int i = 0; i < R; i++) {
			String str = br.readLine();
			for (int j = 0; j < C; j++) {
				map[i][j] = str.charAt(j);
			}
		}
		result = 0;
		isSelected = new boolean[R][C];
		for (int i = 0; i < R; i++) {
			check = false;
			pipe(i, 0);
			 
		}
		System.out.println(result);
		br.close();
	}

	static void pipe(int r, int c) {
		if (c == C - 1) { // 빵집과 만나면 파이프라인 하나 완성
			result++;
			check = true;
			return;
            
            // 파이프라인 하나를 완성하고 나면 남은 행들도 다 확인해야한다고 생각했었다.
            // 그래서 엉뚱하게 접근했고, 경우의 수가 너무너무 늘어나는 것 같아 잘못된 것을 알았다... 
//			if (startRow + 1 < R) {
//				pipe(startRow + 1, 0, startRow + 1, cnt + 1);
//			} else {
//				result = Math.max(cnt, result);
//				return;
//			}
		}

		for (int i = 0; i < dr.length; i++) {
			int nr = r + dr[i];
			int nc = c + dc[i];
			if (0 <= nr && nr < R && 0 <= nc && nc < C && !isSelected[nr][nc] && map[nr][nc] != 'x') {

				// 범위 안에 들어오고 벽이 아니고, 선택이 겹치면 안 되므로
				isSelected[nr][nc] = true; //
				pipe(nr, nc);
				if(check) return;
			}
		}
		// 세 방향 확인했는데 못 가면
		return;
	}
}