题目：

有一个宽为W个小格，高为H个小格，总小格数为W*H的棋盘。棋盘中，可以被涂色的小格用"P"标识，不可以涂色的小格用"B"标识，可以涂色也可以选择不涂色的小格用"?"标识。如下W=5， H=4的棋盘

PPPBB

PP?BB

PP?PP

BBP?P

有一个儿童，手中有1*1 ， 2*2， 3*3 等方形图章。这个孩子希望用手中的最大的图章，将棋盘中所有可以被涂色的P标识的方格都盖满。其中"?"标识的小格可以被涂色，也可以不被涂色。

上面W=5， H=4的棋盘，可以将涂色区域盖满的图章为3*3

求：用最大的那个图章，可以将所有的P小格都盖上颜色，返回图章的边长

 

思路1：硬遍历+剔除无效的解

首先，先找出横向的连续区域，取其最小的那一个

然后以最小连续区域的最小值作为最大的图章

从左上角依次盖章：如果能盖下，就盖。不能的话顺序移动一个位置，继续盖

最后盖章完成后，检测是否有P格没有被盖上

 

代码：

public static boolean CanBePaint(char[][] Canvas, int X, int Y, int Size){        for(int i=X; i+Size < Canvas.length-1; i++){            for(int j=Y; j+Size < Canvas[i].length-1; j++){                    if(Canvas[i][j] == 'B'){                    return false;                }            }        }        return true;    }        public static char[][] Paint(char[][] Canvas, int X, int Y, int Size){        for(int i=X; i+Size < Canvas.length-1; i++){            for(int j=Y; j+Size < Canvas[i].length-1; j++){                    Canvas[i][j]= '#';            }        }        return Canvas;    }        public static boolean CheckAllPaint(char[][] Canvas){        for(int X=0;X< Canvas.length; X++){            for(int Y=0;Y < Canvas[X].length; Y++){                    if(Canvas[X][Y] == 'P'){                    return false;                }            }        }        return true;    }        public static int getMaxLength(char[][] Canvas){        int iMaxTotal=0;        int iMaxW=Canvas[0].length;        int iMaxH=Canvas.length;                   int iMaxLine = 0;        int iCounter  = 0;        int pCounter = 0;                        for(int H=0;H< Canvas.length; H++){                        iMaxLine = 0;            iCounter  = 0;            pCounter = 0;                        for(int W=0;W< Canvas[H].length; W++){                if(Canvas[H][W] =='P' || Canvas[H][W] =='?'){                    iCounter++;                    pCounter++;                    if(iMaxLine 
     
       iCounter  ){                    iMaxLine = iCounter;                }            }        }        /*        if(iMaxW > iMaxH){            iMaxTotal = iMaxH;        }        else{            iMaxTotal = iMaxW;        }        */                return iMaxLine;    }            public static int SBPaint(char[][] Canvas){        int Stamp = 1;                int iMax = getMaxLength(Canvas);                for(int Size = iMax;Size>1;Size-- ){            char[][] TempCanvas = Canvas;            for(int X=0;X+iMax < Canvas.length; X++){                for(int Y=0;Y+iMax < Canvas[X].length; Y++){                        if(CanBePaint(TempCanvas,X,Y,Size)){                        TempCanvas = Paint(TempCanvas,X,Y,Size);                    }                }            }                        if(CheckAllPaint(TempCanvas)){                Stamp = Size;                break;            }        }        return Stamp;    }
     

 

 

思路2：直接找出横向和纵向的连续区域，取其最小的那一个 （不知道这个对不对）

 

PS：此文为了纪念两个多月来的努力，感谢儿子昨天晚上仅哭闹了一次，让爸爸睡了个好觉。