洛谷P1331-搜索基础-什么是矩形？(我的方案)

原题链接：https://www.luogu.com.cn/problem/P1331

简单来说就是给出一个由‘#’和‘.‘组成的矩阵。需要识别存在几个矩形(被完全填充的)。如果有矩形相互衔接则认为出错。

那么如何识别矩形呢？关于矩形的思考有以下的三种：

1、对于r行c列的矩阵，1表示有效0表示无效。以行优先的方式遍历，如果在点(i,k)处出现一个1则进行以下操作：k不变递增i直到i为0作边界。获取第i行的长度len并遍历i+1以后有效的每一行，依次确定长度是否与len相等即可。实现的代码如下：

 1 bool check(int x,int y)
 2 {
 3     int endx=x;
 4     while(endx<r&&aim[endx][y])endx++;
 5     //遍历行边界 
 6     int i=x;
 7     int k=y;
 8     while(k<c&&aim[i][k]){aim[i][k]=0;k++;}
 9     int endy = k;
10     //遍历第一行的列边界
11     for(i++;i<endx;i++)
12     {//控制行 
13         for(k=y;k<c;k++)
14         {//控制列 
15             if(!aim[i][k])break;
16             aim[i][k]=0;
17         }
18         if(k!=endy)return false;
19         //注意是不等于 
20     }
21     return true;
22 }
23 
24 int solve()
25 {
26     int couts=0;
27     for(int i=0;i<r;i++)
28     {
29         for(int k=0;k<c;k++)
30         {
31             if(aim[i][k])
32             {
33                 if(check(i,k))couts++;
34                 else return -1;
35             }
36         }
37     }
38     return couts;
39 }

View Code

但是，有时候的情况并不允许，例如：(0->'.'&&1->'#')

View Code

该思路重视左边界与矩形内部，但是左边界往往不能够照应到整个连通区，所以方案不允许。

2、第二种方案是采用搜索的方式关注了矩形的坐标意义--即四个顶点的坐标关系。具体实现方式就是BFS遍历获取连通块的最极端的四个点后，再比较四个点的几何关系。具体代码如下：

 1 struct point
 2 {
 3     int x,y;
 4 };
 5 int r,c;
 6 int aim[1005][1005];
 7 const int dx[]={0,0,1,-1};
 8 const int dy[]={1,-1,0,0};
 9 int tx[4];
10 int ty[4];
11 
12 bool check(int x,int y)
13 {
14     queue<point> psd;
15     point p;
16     p.x=x; p.y=y; psd.push(p);
17     int nowx,nowy;
18     while(1)
19     {
20         if(psd.empty())break;
21         p=psd.front();psd.pop();
22         nowx=p.x; nowy=p.y;
23         if(aim[nowx][nowy]==0)continue;
24         aim[nowx][nowy]=0;
25         //printf("(%d,%d)
",nowx,nowy);
26         if(tx[0]>=nowx&&ty[0]>=nowy){tx[0]=nowx;ty[0]=nowy;}//左上角
27         if(tx[1]>=nowx&&ty[1]<=nowy){tx[1]=nowx;ty[1]=nowy;}//右上角
28         if(tx[2]<=nowx&&ty[2]>=nowy){tx[2]=nowx;ty[2]=nowy;}//左下角
29         if(tx[3]<=nowx&&ty[3]<=nowy){tx[3]=nowx;ty[3]=nowy;}//右下角
30         for(int i=0;i<4;i++)
31         {
32             int cx=nowx+dx[i];
33             int cy=nowy+dy[i];
34             if(cx>=0&&cy>=0&&cx<r&&cy<c&&aim[cx][cy])
35             {
36                 p.x=cx;p.y=cy;psd.push(p);
37             }
38         }
39     }
40     /*for(int i=0;i<4;i++)
41     {
42         printf("tx[%d]=%d,ty[%d]=%d
",i,tx[i],i,ty[i]);
43     }*/
44     bool ok;
45     ok=(ty[0]==ty[2])&&(ty[1]==ty[3]);
46     ok=ok&&(tx[0]==tx[1])&&(tx[2]==tx[3]);
47     return ok;
48 }

View Code

该方案仍然错误，因为对于任何一个矩形边框它都可以认为边框是合法的。也就是说该算法忽略了矩形的内部。

3、第二种方案其实基本上摸清了矩形的特征，只要解决“边框”问题就可以。也就是说要保证BFS遍历过的点数。其实只需要增加一个点数计数变量pointnum即可。BFS后直接根据四个顶点的坐标计算出应有的点的个数，比较即可。于是将上述代码更改如下：

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<iostream>
  4 #include<queue>
  5 using namespace std;
  6 struct point
  7 {
  8     int x,y;
  9 };
 10 int r,c;
 11 int aim[1005][1005];
 12 const int dx[]={0,0,1,-1};
 13 const int dy[]={1,-1,0,0};
 14 int tx[4];
 15 int ty[4];
 16 
 17 bool check(int x,int y)
 18 {
 19     int pointnum=0;
 20     queue<point> psd;
 21     point p;
 22     p.x=x; p.y=y; psd.push(p);
 23     int nowx,nowy;
 24     while(1)
 25     {
 26         if(psd.empty())break;
 27         p=psd.front();psd.pop();
 28         nowx=p.x; nowy=p.y;
 29         if(aim[nowx][nowy]==0)continue;
 30         aim[nowx][nowy]=0;
 31         //printf("(%d,%d)
",nowx,nowy);
 32         pointnum++;
 33         if(tx[0]>=nowx&&ty[0]>=nowy){tx[0]=nowx;ty[0]=nowy;}//左上角
 34         if(tx[1]>=nowx&&ty[1]<=nowy){tx[1]=nowx;ty[1]=nowy;}//右上角
 35         if(tx[2]<=nowx&&ty[2]>=nowy){tx[2]=nowx;ty[2]=nowy;}//左下角
 36         if(tx[3]<=nowx&&ty[3]<=nowy){tx[3]=nowx;ty[3]=nowy;}//右下角
 37         for(int i=0;i<4;i++)
 38         {
 39             int cx=nowx+dx[i];
 40             int cy=nowy+dy[i];
 41             if(cx>=0&&cy>=0&&cx<r&&cy<c&&aim[cx][cy])
 42             {
 43                 p.x=cx;p.y=cy;psd.push(p);
 44             }
 45         }
 46     }
 47     bool ok;
 48     ok=(ty[0]==ty[2])&&(ty[1]==ty[3]);
 49     ok=ok&&(tx[0]==tx[1])&&(tx[2]==tx[3]);
 50     int s=(ty[1]-ty[0]+1)*(tx[2]-tx[0]+1);
 51     ok=ok&&(s==pointnum);
 52     //printf("pointnum->%d
",pointnum);
 53     return ok;
 54 }
 55 
 56 int solve()
 57 {
 58     int couts=0;
 59      for(int i=0;i<r;i++)
 60      {
 61          for(int k=0;k<c;k++)
 62          {
 63              if(aim[i][k])
 64             {
 65                 for(int p=0;p<4;p++)
 66                 {
 67                     tx[p]=i;ty[p]=k;
 68                 }
 69                 if(check(i,k))couts++;
 70                 else return -1;
 71              }
 72          }
 73          //printf("ok
");
 74      }
 75      return couts;
 76 }
 77 
 78 int main()
 79 {
 80     //freopen("input.txt","r",stdin);
 81     while(cin>>r>>c)
 82     {
 83         memset(aim,0,sizeof(aim));
 84         getchar();
 85         for(int i=0;i<r;i++)
 86         {
 87             for(int k=0;k<c;k++)
 88             {
 89                 char m;cin>>m;
 90                 if(m=='#')aim[i][k]=1;
 91             }
 92             getchar();
 93         }
 94         for(int i=0;i<r;i++)
 95         {
 96             for(int k=0;k<c;k++)
 97             {
 98                 if(aim[i][k])printf("1");
 99                 else printf("0");
100             }
101             printf("
");
102         }
103         printf("
");
104         //
105         int num=solve();
106         if(num==-1)printf("Bad placement.
");
107         else printf("There are %d ships.
",num);
108         /*for(int i=0;i<r;i++)
109         {
110             for(int k=0;k<c;k++)
111             {
112                 if(aim[i][k])printf("%2d",1);
113                 else printf("  ");
114             }
115             printf("
");
116         }
117         printf("
");*/
118     }
119     return 0;
120 }

View Code

提交后完美解决。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<queue>
 5 using namespace std;
 6 struct point
 7 {
 8     int x,y;
 9 };
10 int r,c;
11 int aim[1005][1005];
12 const int dx[]={0,0,1,-1};
13 const int dy[]={1,-1,0,0};
14 int tx[4];
15 int ty[4];
16 
17 bool check(int x,int y)
18 {
19     int pointnum=0;
20     queue<point> psd;
21     point p;
22     p.x=x; p.y=y; psd.push(p);
23     int nowx,nowy;
24     while(1)
25     {
26         if(psd.empty())break;
27         p=psd.front();psd.pop();
28         nowx=p.x; nowy=p.y;
29         if(aim[nowx][nowy]==0)continue;
30         aim[nowx][nowy]=0;
31         pointnum++;
32         if(tx[0]>=nowx&&ty[0]>=nowy){tx[0]=nowx;ty[0]=nowy;}//左上角
33         if(tx[1]>=nowx&&ty[1]<=nowy){tx[1]=nowx;ty[1]=nowy;}//右上角
34         if(tx[2]<=nowx&&ty[2]>=nowy){tx[2]=nowx;ty[2]=nowy;}//左下角
35         if(tx[3]<=nowx&&ty[3]<=nowy){tx[3]=nowx;ty[3]=nowy;}//右下角
36         for(int i=0;i<4;i++)
37         {
38             int cx=nowx+dx[i];
39             int cy=nowy+dy[i];
40             if(cx>=0&&cy>=0&&cx<r&&cy<c&&aim[cx][cy])
41             {
42                 p.x=cx;p.y=cy;psd.push(p);
43             }
44         }
45     }
46     bool ok;
47     ok=(ty[0]==ty[2])&&(ty[1]==ty[3]);
48     ok=ok&&(tx[0]==tx[1])&&(tx[2]==tx[3]);
49     int s=(ty[1]-ty[0]+1)*(tx[2]-tx[0]+1);
50     ok=ok&&(s==pointnum);
51     return ok;
52 }
53 
54 int solve()
55 {
56     int couts=0;
57      for(int i=0;i<r;i++)
58      {
59          for(int k=0;k<c;k++)
60          {
61              if(aim[i][k])
62             {
63                 for(int p=0;p<4;p++)
64                 {
65                     tx[p]=i;ty[p]=k;
66                 }
67                 if(check(i,k))couts++;
68                 else return -1;
69              }
70          }
71      }
72      return couts;
73 }
74 
75 int main()
76 {
77     while(cin>>r>>c)
78     {
79         memset(aim,0,sizeof(aim));
80         getchar();
81         for(int i=0;i<r;i++)
82         {
83             for(int k=0;k<c;k++)
84             {
85                 char m;cin>>m;
86                 if(m=='#')aim[i][k]=1;
87             }
88             getchar();
89         }
90         //
91         int num=solve();
92         if(num==-1)printf("Bad placement.
");
93         else printf("There are %d ships.
",num);
94     }
95     return 0;
96 }

提交的代码