原题链接
考察:dfs,思维
思路:
实际答案最大是2.因为如果存在拐角的正方形,那么可以去掉包围它的两个正方形.如果不存在,答案就是1.假设当前正方形数\(<3\),那么答案就是\(-1\).
Code
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 55;
int m,n,cnt,p[N*N];
bool vis[N][N];
int xx[4] = {-1,1,0,0},yy[4] = {0,0,-1,1};
char mp[N][N],back[N][N];
struct Node{
int x,y,cnt;
bool operator<(const Node& ns){
return this->cnt<ns.cnt;
}
}node[N*N];
int dfs(int x,int y)
{
vis[x][y] = 1;
int cnt = 1;
for(int i=0;i<4;i++)
{
int dx = x+xx[i],dy = y+yy[i];
if(dx>0&&dx<=m&&dy>0&&dy<=n&&mp[dx][dy]=='#'&&!vis[dx][dy])
cnt += dfs(dx,dy);
}
return cnt;
}
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++) scanf("%s",mp[i]+1);
//最多只会去掉2,因为拐角处想连接必须有2个正方形
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
if(mp[i][j]=='#')
{
node[cnt].x = i;
node[cnt++].y = j;
}
}
if(cnt<3) puts("-1");
else{
bool ok = 1;
for(int i=0;i<cnt;i++)
{
mp[node[i].x][node[i].y] = '.';
memset(vis,0,sizeof vis);
int s = dfs(node[(i+1)%cnt].x,node[(i+1)%cnt].y);
mp[node[i].x][node[i].y] = '#';
if(s!=cnt-1) ok = 0;
}
if(!ok) puts("1");
else puts("2");
}
return 0;
}