题目链接:
题目大意:
n*m的网格,线只能在网格的顶点处才能从布的一面穿到另一面。每一段线都覆盖一个单位网格的两条对角线之一,而在绣的过程中,一针中连续的两段线必须分处布的两面。
给出布两面的图案,问最少需要几针才能绣出来?一针是指针不离开布的一次绣花过程。
题目思路:
【宽搜】或【并查集】
正面的如果有线就把端点连正边,反面连负边。
一针就是从正边到反边再到正边这样循环下去。用宽搜写floodfill(或者并查集)把一次走到线路抠出来,线路上|正边数-反边数|/2为该线路的针数。
感觉自己说不太清楚,引用大牛zhymaoiing的话:
将正面的边视为正边,反面的则视为负边。用floodfill将由正边和负边交替连接的结点组成一个块。对于每一个块,其中的所有结点的正边数目和负边数目之差的绝对值(定为dep)之后div 2后就为这个块的所需针数。
在一个块中只用一针就可完成,假设该针由v1出发,到vn结束,那么v1到vn中间的点的dep为0,而v1和vn则为1。也就是说块中的那一针在v1有一个入口,在vn有一个出口,而每一对入口和出口就代表了一针,那么就可以通过dep之和除以2得到所需针数。由此可以拓宽到多针。
BFS
/
//by coolxxx
//
#include<iostream>
#include<algorithm>
#include<string>
#include<iomanip>
#include<memory.h>
#include<time.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<math.h>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define abs(a) ((a)>0?(a):(-(a)))
#define lowbit(a) (a&(-a))
#define sqr(a) ((a)*(a))
#define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b))
#define eps 1e-8
#define J 10
#define MAX 0x7f7f7f7f
#define PI 3.1415926535897
#define N 207
using namespace std;
int n,m,lll,ans,cas;
char map[][N][N];
bool u[N][N];
bool f;
void floodfill(int i,int j)
{
int t=,k;
if(u[i][j])return;
u[i][j]=;
if(i> && j>)
{
for(k=;k<;k++)
{
if(map[k][i-][j-]=='\\' || map[k][i-][j-]=='X')
{
t=t+(-)*k+;
f=;
floodfill(i-,j-);
}
}
}
if(i> && j<=m)
{
for(k=;k<;k++)
{
if(map[k][i-][j]=='/' || map[k][i-][j]=='X')
{
t=t+(-)*k+;
f=;
floodfill(i-,j+);
}
}
}
if(i<=n && j>)
{
for(k=;k<;k++)
{
if(map[k][i][j-]=='/' || map[k][i][j-]=='X')
{
t=t+(-)*k+;
f=;
floodfill(i+,j-);
}
}
}
if(i<=n && j<=m)
{
for(k=;k<;k++)
{
if(map[k][i][j]=='\\' || map[k][i][j]=='X')
{
t=t+(-)*k+;
f=;
floodfill(i+,j+);
}
}
}
lll+=abs(t);
}
int main()
{
#ifndef ONLINE_JUDGE
// freopen("1.txt","r",stdin);
// freopen("2.txt","w",stdout);
#endif
int i,j,k;
// while(~scanf("%s",s1))
while(~scanf("%d",&n))
// for(scanf("%d",&cas),l=1;l<=cas;l++)
{
memset(u,,sizeof(u));
ans=;
scanf("%d",&m);
for(k=;k<;k++)
for(i=;i<=n;i++)
scanf("%s",map[k][i]+);
for(i=;i<=n+;i++)
{
for(j=;j<=m+;j++)
{
lll=f=;
floodfill(i,j);
if(f && lll==)ans++;
else ans+=lll/;
}
}
printf("%d\n",ans);
}
return ;
} /*
// //
*/
千万不要点
并查集
//
//by coolxxx
//
#include<iostream>
#include<algorithm>
#include<string>
#include<iomanip>
#include<memory.h>
#include<time.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<math.h>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define abs(a) ((a)>0?(a):(-(a)))
#define lowbit(a) (a&(-a))
#define sqr(a) ((a)*(a))
#define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b))
#define eps 1e-8
#define J 10
#define MAX 0x7f7f7f7f
#define PI 3.1415926535897
#define N 207
using namespace std;
int n,m,lll,ans,cas,cass;
int a[N*N],b[N*N],fa[N*N],c[N*N];
bool u[N*N],v[N*N];
char map[][N][N];
int zhao(int aa)
{
if(fa[aa]==-)return aa;
return fa[aa]=zhao(fa[aa]);
}
int main()
{
#ifndef ONLINE_JUDGE
// freopen("1.txt","r",stdin);
// freopen("2.txt","w",stdout);
#endif
int i,j,k,x,y,fx,fy;
// while(~scanf("%s",s1))
while(~scanf("%d",&n))
// for(scanf("%d",&cas),cass=1;cass<=cas;cass++)
{
memset(fa,-,sizeof(fa));
memset(a,,sizeof(a));
memset(b,,sizeof(b));
memset(u,,sizeof(u));
memset(v,,sizeof(v));
ans=;c[]=;
scanf("%d",&m);
for(k=;k<;k++)
for(i=;i<n;i++)
scanf("%s",map[k][i]);
for(k=;k<;k++)
{
for(i=;i<n;i++)
{
for(j=;j<m;j++)
{
if(map[k][i][j]=='\\' || map[k][i][j]=='X')
{
x=i*(m+)+j;y=(i+)*(m+)+j+;
fx=zhao(x);fy=zhao(y);
if(fx!=fy)
fa[fy]=fx;
a[x]+=(-)*k+;
a[y]+=(-)*k+;
v[x]=v[y]=;
}
if(map[k][i][j]=='/' || map[k][i][j]=='X')
{
x=i*(m+)+j+;y=(i+)*(m+)+j;
fx=zhao(x);fy=zhao(y);
if(fx!=fy)
fa[fy]=fx;
a[x]+=(-)*k+;
a[y]+=(-)*k+;
v[x]=v[y]=;
}
}
}
}
for(i=;i<(n+)*(m+);i++)
{
if(!v[i])continue;
j=zhao(i);
if(!u[j])u[j]=,c[++c[]]=j;
b[j]+=abs(a[i]);
}
for(i=;i<=c[];i++)
{
if(b[c[i]]==)ans++;
else ans+=b[c[i]]/;
}
printf("%d\n",ans);
}
return ;
} /*
// //
*/
千万不要点