Gym102411C Cross-Stitch

Link
先补成这样：
然后找交错欧拉回路即可。
具体为什么能找到我也不知道。

#include<set>
#include<cctype>
#include<cstdio>
#include<vector>
#include<utility>
int n,m,id[107][107];std::multiset<int>e[10207][2];std::vector<int>ans;
char get(){char c=getchar();while(isspace(c))c=getchar();return c;}
void add(int u,int v,int o){e[u][o].insert(v),e[v][o].insert(u);}
void dfs(int u,int o){for(int v;e[u][o].size();) v=*e[u][o].begin(),e[u][o].erase(e[u][o].begin()),e[v][o].erase(e[v][o].find(u)),dfs(v,!o),ans.push_back(u);}
int main()
{
    scanf("%d%d",&n,&m);int root;
    for(int i=0;i<=n;++i) for(int j=0;j<=m;++j) id[i][j]=i*(m+1)+j;
    for(int j=0;j<m;++j) for(int i=0;i<n;++i) if(get()=='X') add(id[i][j],id[i+1][j+1],1),add(id[i][j+1],id[i+1][j],1),add(id[i][j],id[i+1][j],0),add(id[i][j+1],id[i+1][j+1],0),root=id[i][j];
    dfs(root,1),printf("%d
",(int)ans.size()-1);
    for(int x:ans) printf("%d %d
",x/(m+1),x%(m+1));
}