上方题目链接。

本关卡需要用到的技能：二分图最大匹配。

好了，我们来分析一下题目：

只有墙能阻断激光，
我们先只考虑一行，如果有一面墙，那它的左边的所有空地总共只能放一个机器人，右边也是如此。

相当于一面墙把这一行划分成了两个区域，区域内最多只能放一个机器人（全文重点），使得两个区域都是安全的。

那对于整张图（就是多了几行）我们也可以划分成若干区域，每个区域还是安全的。

同样的，我们对纵向也这样处理，如果横向区域和纵向区域没有重合，那答案就是区域总数了。

很可惜，重合是很可能的（很显然嘛）。

重合会导致一个机器人放到了某个位置占用了这个位置所在的横、纵区域。

怎么办？凉拌

再想想：

对于某个横向区域A，机器人可以放在区域内的任一空地,假设有空地1，空地2，

放在空地1会占用纵向区域B1，放在空地2占用纵向区域B2，被占用的区域不能再放。

是不是感觉答案呼之欲出，没错，就是暴力二分图最大匹配。

我们把横向区域看作左部点，纵向区域看作右部点，每个空地当成边，连接它所在的横、纵区域。

最后用匈牙利算法即可（喜欢最大流也一样啦）。

最后一个问题：墙为什么不能反弹？

答：反弹会自己打自己呀，机器人还不想死呢。

代码在这：

#include<cstdio>
#include<cstring>
using namespace std;
int n,m;
char map[55][55];
struct bian
{
    int y,next;
}a[2600];int last[1300],len;
void ins(int x,int y)
{
    a[++len].y=y;
    a[len].next=last[x];last[x]=len;
}
int h[55][55],l[55][55],sh,sl;
int match[1300];
bool chw[1300];
bool find(int x)
{
    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;
        if(!chw[y])
        {
            chw[y]=true;
            if(match[y]==0||find(match[y]))
            {
                match[y]=x;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    int t;scanf("%d",&t);
    for(int tt=1;tt<=t;tt++)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)scanf("%s",map[i]+1);
        sh=0;
        for(int i=1;i<=n;i++)
        {
            int j=1;
            while(j<=m)
            {
                while(j<=m&&map[i][j]=='#')j++;
                if(j<=m)sh++;
                while(j<=m&&map[i][j]!='#')h[i][j++]=sh;
            }
        }
        sl=0;
        for(int i=1;i<=m;i++)
        {
            int j=1;
            while(j<=n)
            {
                while(j<=n&&map[j][i]=='#')j++;
                if(j<=n)sl++;
                while(j<=n&&map[j][i]!='#')l[j++][i]=sl;
            }
        }
        memset(last,0,sizeof(last));len=0;
        for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)if(map[i][j]=='o')ins(h[i][j],l[i][j]);
        int ans=0;
        memset(match,0,sizeof(match));
        for(int i=1;i<=sh;i++)
        {
            memset(chw,false,sizeof(chw));
            if(find(i))ans++;
        }
        printf("Case :%d\n%d\n",tt,ans);
    }
    return 0;
}