记录编号	394202	评测结果	AAAAAAAAAA
题目名称	[ZOJ 1654]放置机器人	最终得分	100
用户昵称	Hallmeow	是否通过	通过
代码语言	C++	运行时间	0.066 s
提交时间	2017-04-13 09:01:43	内存使用	35.64 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 1000
#define pos(i,a,b) for(int i=(a);i<=(b);i++)
using namespace std;
int n,m;//n行m列 
struct haha
{
       int qix,qiy,zhongx,zhongy,jikong;
       int kong[N][4];
};
haha hang[N];
haha lie[N];
int a[N][N];
int jihang=1,jilie=1;
char cun[N][N];
void searchhang(int i)
{
     pos(j,1,m)
     {
        if(cun[i][j]=='o')
        {
           if(hang[jihang].qix==0&&hang[jihang].qiy==0)
           {
              hang[jihang].qix=i;hang[jihang].qiy=j;
              
           }
           hang[jihang].kong[++hang[jihang].jikong][1]=i;
           hang[jihang].kong[hang[jihang].jikong][2]=j;
           if(cun[i][j+1]=='#'||j==m)
           {
              hang[jihang].zhongx=i;hang[jihang].zhongy=j;
              jihang++;
           }
        }
        if(cun[i][j]=='*')
        {
           if(hang[jihang].qix==0&&hang[jihang].qiy==0)
           {
              hang[jihang].qix=i;hang[jihang].qiy=j;
              
           }
           if(cun[i][j+1]=='#'||j==m)
           {
              hang[jihang].zhongx=i;hang[jihang].zhongy=j;
              jihang++;
           }
        }
        if(cun[i][j]=='#')
          continue;
     }
     if(i==n)
      return;
     searchhang(i+1);
}
void searchlie(int j)
{
     pos(i,1,n)
     {
        if(cun[i][j]=='o')
        {
           if(lie[jilie].qix==0&&lie[jilie].qiy==0)
           {
              lie[jilie].qix=i;lie[jilie].qiy=j;
              
           }
           lie[jilie].kong[++lie[jilie].jikong][1]=i;
           lie[jilie].kong[lie[jilie].jikong][2]=j;
           if(cun[i+1][j]=='#'||i==n)
           {
              lie[jilie].zhongx=i;lie[jilie].zhongy=j;
              jilie++;
           }
        }
        if(cun[i][j]=='*')
        {
           if(lie[jilie].qix==0&&lie[jilie].qiy==0)
           {
              lie[jilie].qix=i;lie[jilie].qiy=j;
              
           }
           if(cun[i+1][j]=='#'||i==n)
           {
              lie[jilie].zhongx=i;lie[jilie].zhongy=j;
              jilie++;
           }
        }
        if(cun[i][j]=='#')
          continue;
     }
     if(j==m)
      return;
     searchlie(j+1);
}
bool flag[N];
int match[N];
bool find(int p)
{
     pos(i,1,jilie)
     {
        if(a[p][i]==1&&flag[i]==0)
        {
           flag[i]=1;
           if(match[i]==0||find(match[i]))
           {
             match[i]=p;
             return true;
           }
        }
     }
     return false;
}
int main()
{
    freopen("placetherobots.in","r",stdin);
    freopen("placetherobots.out","w",stdout);
    scanf("%d%d",&n,&m);
    pos(i,1,n)
      pos(j,1,m)
         cin>>cun[i][j];
    searchhang(1);
    searchlie(1);
    jihang--;
    jilie--;
    pos(i,1,jihang)
    {
      pos(j,1,jilie)
      { 
         int xx=hang[i].qix;int kk=0;int yy=lie[j].qiy;
       if(hang[i].qix>=lie[j].qix&&hang[i].qix<=lie[j].zhongx&&lie[j].qiy>=hang[i].qiy&&lie[j].qiy<=hang[i].zhongy)
       {
         pos(k,1,hang[i].jikong)
          if(hang[i].kong[k][1]==xx&&hang[i].kong[k][2]==yy)
          {
            kk=1;
            //break;
          }
        pos(k,1,lie[j].jikong)
          if(lie[j].kong[k][1]==xx&&lie[j].kong[k][2]==yy)
          {
            a[i][j]=1;
           // break;
          }
       }
      }
    }
    int ans=0;
    pos(i,1,jihang)
    {
              memset(flag,0,sizeof(flag));
              if(find(i))
                ans++;
    }
    cout<<ans;
    //while(1);
    return 0;
}