• [1556] Flandre at Minecraft

  • 时间限制: 1000 ms 内存限制: 65535 K
  • 问题描述

  • XadillaX built two "Flandres" in his minecraft world.

    You know, they were all built from wool - red wool, yellow wool, black wool, white wool, etc.
    But one day, the big Devil, Hungar wants to destroy Flandre!

    The method Hungar uses is that to make the Flandre all white! Just like the picture below:

    But Devil Hungar is so stupid that he just can destroy the Flandre by doing such 3 rules below:

    Turn any one block of wool.

    Choose an integer H and turn the first D * H blocks from left to right and from top to bottom.

    Choose an integer G and turn the first D * G blocks from right to left and from bottom to top.

    (Notice that the number H, G may be different at each step)

    The word "turn" above means that if one block is white, then Hungar will turn it to colorful and if that block is other color, Hungar will turn it to white.
    D is the lucky number of Devil Hungar.
    For example, if Hungar wants to turn first 16 blocks from left to right and from top to bottom at a 12 * 12 Flandre, the whole blocks at the toppest and the first 4 blocks from left to right at the second toppest layer will be turned.

    Now give you the side length of a "Flandre" and each pixel of it, you have to calculate out the minimum steps Hungar have to cost to destroy the "Flandre" so that XadillaX can get ready for the war as soon as possible.


    Note: It guarantee that D divides N * N!


  • 输入
  • This problem contains several cases and ends with EOF.
    The first line of each case contains 2 integers N (1 < N <= 50) and D (1 <= D <= N * N), means the side length of Flandre and the lucky number of Hungar's.
    Next follows N lines, each line contains N uppercase letters. "W" means white wool block and the rest ones stand for other colors.
  • 输出
  • For each case, you should output the minimum steps Hungar can destroy the whole "Flandre".
  • 样例输入
  • 16 16
    WBBBBBBBBBBBBRRB
    BPPPPPPPPPPPPRRR
    PPPPPPPPPPPPPRRR
    PPPPPPPPPPPPPPPP
    RPRRRPRRRPRRRPRR
    PPPPPBBPPPPBBPPB
    BBPPBYYBPPBYYBPY
    YYBBYYYYBBYBYYBY
    BYYYYBYYYYYBBYYY
    YYYYBYYBYYYBWBYY
    YYYBWBBWBYBWWWBY
    YYBWWWWWWBWWWWBY
    YYBWRWWWWWWWRWBY
    YYBWRWWWWWWWRWBY
    YYBWWWWWWWWWWWBY
    BYYBWWWWWWWWWBYY
    
  • 样例输出
  • 40
    
  • 提示
  • 来源
  • XadillaX
  • 操作

显示春菜