2018-07-10 14:46:34

dalao们用的是数学，来一发纯模拟的： 先贴一发40分代码（连样例都过不了的）:

#include <bits/stdc++.h>
using namespace std;
int n;int a[505][505];
int t1,t2,t3,t4,dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};
struct Node{int x,y;};
queue<Node> q;
void bfs(int x,int y,int clr) //bfs填充
{
while (!q.empty()) q.pop();
q.push({x,y});
while (!q.empty())
{
Node nd = q.front();q.pop();
if (a[nd.x][nd.y]) continue;
a[nd.x][nd.y] = clr;
for (int i = 0;i < 4;i++)
{
int nx = nd.x + dx[i],ny = nd.y + dy[i];
if (nx >= 0 && nx <= 500 && ny >= 0 && ny <= 500) q.push({nx,ny}); //扩展
}
}
}
int main ()
{
scanf("%d",&n);
int sx = 0,sy = 0;
for (int i = 0;i <= n;i++) //为封口，多做一轮
{
if (i != n) scanf("%d%d",&t1,&t2); else t1 = sx,t2 = sy;//else的一步用来封口
t1 += 250;t2 += 250;
//t1,t2:新读进来的;t3,t4:上一步的
if (i)
{
if (t1 == t3)
{
int mv = min(t2,t4),mx = t2 + t4 - mv;//新的坐标和旧的坐标之间连线，mv为坐标较小的，mx为坐标较大的，下同
for (int i = mv;i <= mx;i++) a[t1][i] = 1;
}
else
{
int mv = min(t1,t3),mx = t1 + t3 - mv;
for (int i = mv;i <= mx;i++) a[i][t2] = 1;
}
}
else
{
sx = t1 - 250;sy = t2 - 250;
//只读了一个点
}
t3 = t1;t4 = t2;//更新旧值
}

bfs(0,0,-1);//填充外面的，用-1表示
for (int i = 0;i <= 500;i++)
for (int j = 0;j <= 500;j++)
if (a[i][j] == 0) bfs(i,j,1);//填充里面的，用1表示
int ans = 0;
for (int i = 0;i <= 500;i++)
for (int j = 0;j <= 500;j++)
if (a[i][j] == 1 && a[i + 1][j] == 1
&& a[i][j + 1] == 1 && a[i + 1][j + 1] == 1) ++ans;//每当有2*2的一个全部由1组成的正方形出现时，面积就加1（四个1对应四个点）
printf("%d\n",ans);
return 0;
}

1 1 1 0

1 1 1 1

1 1 1 1

1 1 1 0

1 1 1 1

1 1 1 1

1 1 1 1

(3，2）到（3，1）有一条线，则绘图效果和上面那个矩阵一样：凹进去的部分被“填补了”

#include <bits/stdc++.h>
using namespace std;
int n;int a[2005][2005];
int t1,t2,t3,t4,dx[] = {1,0,-1,0},dy[] = {0,1,0,-1},lx = 1001,ly = 1001,
rx = -1,ry = -1;
struct Node{int x,y;};
queue<Node> q;
void bfs(int x,int y,int clr)
{
while (!q.empty()) q.pop();
q.push({x,y});
while (!q.empty())
{
Node nd = q.front();q.pop();
if (a[nd.x][nd.y]) continue;
a[nd.x][nd.y] = clr;
for (int i = 0;i < 4;i++)
{
int nx = nd.x + dx[i],ny = nd.y + dy[i];
if (nx >= lx && nx <= rx && ny >= ly && ny <= ry) q.push({nx,ny});
}
}
}
int main ()
{
scanf("%d",&n);
int sx = 0,sy = 0,ssx,ssy;
scanf("%d%d",&sx,&sy);sx += 1001;sy += 1001;a[sx][sy] = 1;t3 = sx;t4 = sy;
ssx = sx;ssy = sy;//sx,sy表示当前勾线位置
//ssx，ssy表示第一个点
lx = min(lx,ssx);ly = min(ly,ssy);rx = max(rx,ssx);ry = max(ry,ssy);
//lx,ly左上角坐标，rx,ry右下角坐标，是一个优化
for (int i = 1;i <= n;i++)
{
if (i != n)
{
scanf("%d%d",&t1,&t2);t1 += 1001;t2 += 1001;//加1000刚好会RE，悲哀，我在这个地方卡了半个小时
}
else t1 = ssx,t2 = ssy;
if (t1 == t3)
{
int dis = 2 * abs(t2 - t4);//距离，下同
if (t2 < t4)
{
for (int i = 1;i <= dis;i++) a[sx][++sy] = 1;
}
else
{
for (int i = 1;i <= dis;i++) a[sx][--sy] = 1;
}
}
else
{
int dis = 2 * abs(t1 - t3);
if (t1 < t3)
{
for (int i = 1;i <= dis;i++) a[++sx][sy] = 1;
}
else
{
for (int i = 1;i <= dis;i++) a[--sx][sy] = 1;
}
}

t3 = t1;t4 = t2;
lx = min(lx,sx);ly = min(ly,sy);rx = max(rx,sx);ry = max(ry,sy);//更新左上角，右下角
}
lx--;rx++;ly--;ry++;//将外面一圈连起来
bfs(lx,ly,-1);
for (int i = lx;i <= rx;i++)
for (int j = ly;j <= ry;j++)
if (a[i][j] == 0)
{
bfs(i,j,1);break;
}
int ans = 0;
for (int i = lx;i <= rx;i++)
for (int j = ly;j <= ry;j++)
if (a[i][j] == 1 && a[i + 1][j] == 1
&& a[i][j + 1] == 1 && a[i + 1][j + 1] == 1) ++ans;
printf("%d\n",ans / 4);
return 0;
}
• star
首页