Các con bò có hệ thống laser mới để trò chuyện thoải mái ngoài đồng cỏ, được mô hình hóa bằng lưới $W \times H$ điểm ($1 \le W \le 100; 1 \le H \le 100$).

Hệ thống cần một dạng kết nối theo đường nhìn để duy trì liên lạc. Đá và cây cản trở liên lạc, nhưng bò đã mua gương chéo (/ và \ bên dưới) làm tia laser đổi hướng $90$ độ. Bản đồ dưới đây minh họa bài toán.

Trên bản đồ này $H=8$ và $W=7$. Hai con bò liên lạc được ký hiệu $C$; đá và vật cản khác là *:

7 . . . . . . .         7 . . . . . . .
6 . . . . . . C         6 . . . . . /-C
5 . . . . . . *         5 . . . . . | *
4 * * * * * . *         4 * * * * * | *
3 . . . . * . .         3 . . . . * | .
2 . . . . * . .         2 . . . . * | .
1 . C . . * . .         1 . C . . * | .
0 . . . . . . .         0 . \-------/ .
  0 1 2 3 4 5 6           0 1 2 3 4 5 6

Hãy tìm số gương ít nhất $M$ cần lắp để duy trì liên lạc laser giữa hai con bò. Dữ liệu kiểm thử luôn bảo đảm điều này khả thi.

Dữ liệu vào

• Dòng 1: hai số nguyên cách nhau bởi dấu cách: $W$ và $H$.
• Các dòng $2,\ldots,H+1$: toàn bộ đồng cỏ.

Dữ liệu ra

• Dòng 1: một số nguyên $M$.

Ví dụ

Dữ liệu vào 1

7 8
.......
......C
......*
*****.*
....*..
....*..
.C..*..
.......

Dữ liệu ra 1

3

Ghi công bài toán: Rob Kolstad, 2008