Gym 102411 C 十字绣

题意：在w*h(1<=w,h<=100)的布上绣十字绣，要求在给定的方格上连石子，图案正面每段只能走一次。需要在用一根线绣完整幅图，而且使用线的长度最短。在背面可以往相邻8个方向走，而且可以重复。输出一种方案。

观察样例，我们可以大胆猜想背面只需要走横线或竖线，而且每个格子配两条横线或竖线，即最少需要走4*a-1段路径。我们应该可以通过类似奇偶性的方法证明最优方案长度不小于这样4*a-1段。下一步需要构造出这样的方案。

我们需要在横线和斜线上交替走，而且每条边恰好经过一次，可以发现与欧拉路径有关。由于难以处理无向图欧拉回路度数的奇偶性，所以我们尝试对每条边定向，建立有向图的欧拉回路。参照原来有向图有欧拉回路每个点入度与出度相等的条件，这里要求正面入度=反面出度，反面入度=正面出度。一个简单的图块就可以满足这个条件：

然而这样直接拼接起来跑欧拉路径出来并不是完整的图。。。观察一下，会发现这样建出来的图裂开了。。。虽然度数满足要求了，但是要使路径满足第一个条件，图会裂成几个连通块。

我们想办法使构造出来的图连通。最简单的方式，只要把上面的building blocks转转就行了。构造方法就是2*2的块每块的箭头分别指向不同的方向。容易看出这样的图一定是连通的。

```
#include<cstdio>
```
```
#include<cstring>
```
```
#include<algorithm>
```
```
#include<iostream>
```
```
#include<queue>
```
```
#include<map>
```
```
#include<stack>
```
```
#include<cmath>
```
```
#include<set>
```
```
#include<bitset>
```
```
#include<complex>
```
```
#include<cstdlib>
```
```
#include<assert.h>
```

#define inc(i,l,r) for(int i=l;i<=r;i++)

#define dec(i,l,r) for(int i=l;i>=r;i--)

#define link(x) for(edge *j=h[x];j;j=j->next)

```
#define mem(a) memset(a,0,sizeof(a))
```
```
#define ll long long
```
```
#define mid (x+y>>1)
```
```
#define eps 1e-8
```
```
#define succ(x) (1<<(x))
```
```
#define lowbit(x) (x&(-x))
```
```
#define sqr(x) ((x)*(x))
```
```
#define MAXN 200005
```
```
#define nm 20000005
```
```
using namespace std;
```
```
const double pi=acos(-1);
```
```
const ll inf=1e9+7;
```
```
ll read(){
```
```
    ll x=0,f=1;char ch=getchar();
```

    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

```
    return f*x;
```
```
}
```

struct edge{int t;bool st,vis; edge*next;}e[MAXN<<1],*h[MAXN],*o=e;

```
void add(int x,int y, bool st){
```
```
    //cout<<x<<" to "<<y<<'\n';
```

    o->t=y; o->st=st; o->vis=0; o->next=h[x];h[x]=o++;}

```
 
```
```
char a[110][110];
```
```
int ansp[MAXN], al;
```
```
 
```
```
void euler(int u, int st){
```
```
    link(u) if (!j->vis && j->st==st){
```
```
	j->vis=1;
```
```
	euler(j->t,st^1);
```
```
    }
```
```
    ansp[al++]=u;
```
```
}
```
```
 
```
```
 
```
```
int main(){    
```
```
    int w,h;
```
```
    w=read(),h=read();
```
```
    inc(i,1,h) scanf("%s",a[i]+1);
```
```
    int sp=-1;
```
```
    inc(i,1,h) inc(j,1,w){
```
```
	if (a[i][j]=='X'){
```
```
	    if ((i&1) && (j&1)){
```
```
		add((i-1)*(w+1)+j-1,i*(w+1)+j,0);
```
```
		add((i-1)*(w+1)+j,  i*(w+1)+j-1,0);
```
```
		add(i*(w+1)+j-1,(i-1)*(w+1)+j-1,1);
```
```
		add(i*(w+1)+j,(i-1)*(w+1)+j,1);
```
```
		sp=(i-1)*(w+1)+j-1;
```
```
	    }
```
```
	    else if (!(i&1) && !(j&1)){
```
```
		add(i*(w+1)+j,(i-1)*(w+1)+j-1,0);
```
```
		add( i*(w+1)+j-1,(i-1)*(w+1)+j, 0);
```
```
		add((i-1)*(w+1)+j-1,i*(w+1)+j-1,1);
```
```
		add((i-1)*(w+1)+j,i*(w+1)+j, 1);
```
```
		sp=(i)*(w+1)+j;
```
```
		}
```
```
	    else if (!(i&1) && (j&1)){
```
```
		add((i)*(w+1)+j-1,(i-1)*(w+1)+j,0);
```
```
		add((i-1)*(w+1)+j-1,(i)*(w+1)+j,0);
```
```
		add((i-1)*(w+1)+j,(i-1)*(w+1)+j-1,1);
```
```
		add((i)*(w+1)+j,(i)*(w+1)+j-1, 1);
```
```
		sp=(i-1)*(w+1)+j-1;
```
```
	    }
```
```
	    else{
```
```
		add((i-1)*(w+1)+j,(i)*(w+1)+j-1,0);
```
```
		add((i)*(w+1)+j,(i-1)*(w+1)+j-1,0);
```
```
		add((i-1)*(w+1)+j-1,(i-1)*(w+1)+j,1);
```
```
		add((i)*(w+1)+j-1, (i)*(w+1)+j,1);
```
```
		sp=(i)*(w+1)+j;
```
```
		}
```
```
	}
```
```
    }
```
```
    euler(sp,0);
```
```
    printf("%d\n",al-2);
```
```
    dec(i,al-1,1){
```

	printf("%d %d\n",ansp[i]%(w+1),ansp[i]/(w+1));

```
    }
```
```
    return 0;
```
```
}
```

fffasttime

Gym 102411 C 十字绣

发表评论取消回复

发表评论 取消回复

发表评论取消回复