将整个棋盘分为横坐标与纵坐标的和为奇数和偶数的两种，此时，棋盘就变为了一个二分图。仅针对和为奇数的点而言，若这个点为′∗′'*'′∗′，如果它能匹配到邻近的也为′∗′'*'′∗′的点，那么cnt就加二。cnt代表被能覆盖两个星星的牌。而cnt_代表总的星星数。那么最后的结果就是cnt/2+(cnt_-cnt)
#include#include#includeusing namespace std;typedef pairPII;vectorve;char g[105][105];bool st[105][105];int dx[]={1,-1,0,0},dy[]={0,0,1,-1};int n,m;PII match[105][105];bool find(int x,int y){for(int i=0;i>n>>m;int cnt_=0;for(int i=1;ig[i][j];match[i][j]={-1,-1};if(g[i][j]=='*'){cnt_++;}}}int cnt=0;for(int i=1;i