• [B] Count Mountains

  • 时间限制: 1000 ms 内存限制: 65535 K
  • 问题描述
  • Hellow everyone, do you like to climb mountains? It is a good way to enjoy yourself!
    Now, there are some photos, it includes the mountains!!!
    What? Invisibility? Oh Yeah... They are just my paintings! Don't care about these details.
    So, every painting only contain 'x' and '.' where 'x' is a part of mountains, and '.' is a part of sky.
    And every painting has H rows and W columns, rows from bottom to top are from 0 to H-1, columns from left to right are from 0 to W-1.

    Now, I will tell some details.

    1. If I want to draw N mountains, the i-th (0-based index) mountain is described by its peak position (X[i], Y[i]), 0 <= X[i] < W, 0 <= Y[i] < H.
    The code of mountains pruducted follows:
    For 0 <= i < N;
    For 0 <= x < W;
    For 0 <= y <= Y[i] - |x - X[i]|;
    painting[x, y] = 'X';
    2. Others are '.'.

    Finally, I will give you the paintings, can you tell me the minimum number of mountains in it?


  • 输入
  • Input until EOF.
    For each test, first line will contain two integers H and W(1 <= H, W <= 50), means the height and width of each painting.
    Then followed painting(Only contain 'X' and '.').
  • 输出
  • Print the answer.
  • 样例输入
  • 4 6
    ......
    X..X..
    XXXXXX
    XXXXXX
    2 3
    X.X
    XXX
    
  • 样例输出
  • 3
    2
    
  • 提示
  • 来源
  • Hungar
  • 操作

显示春菜