一开始以为是一道DP题，后来发现状态不太好转移
后来看了题解才发现竟然是一道图论+\(dfs\)，确实不太好想
我们把格子上的点抽象成图中的节点，同时开一个数组记录它的入度
如果该点与正面的某一条线相连，我们就把它的入度加\(1\)
如果该点与反面的某一条线相连，我们就把它的入度减\(1\)
那么这一个点所需要的线的数量就是它的入度的绝对值
我们来举一个例子，如果一个点连着\(3\)个正面的线，又连着\(2\)个反面的线
那么\(2\)个正面的线就会和\(2\)个反面的线抵消，也就是转了一圈
而剩下的那一个正面的线必须另用一针
这样，对于每一个联通块，我们统计该联通块内所有节点的入度之和，最后把它除以二
因为一条线的起点和终点我们分别算了一遍
有一种特殊情况就是该联通块所有节点的入度之和为\(0\)
这说明一条线就可以解决，要特判一下
最后要注意字符''在判断的时候要写成'\'，或者用它的\(ASCII\)值\(92\)，否则会报错
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5,maxk=205;
int head[maxn],tot=1,du[maxn],cnt,a[maxk][maxk],bb[maxn],ans,vis[maxn];
struct asd{
int from,to,next;
}b[maxn];
void ad(int aa,int bb,int cc){
b[tot].from=aa;
b[tot].to=bb;
b[tot].next=head[aa];
head[aa]=tot++;
if(cc==0) du[aa]++;
else du[aa]--;
}
char s[maxk][maxk];
void dfs(int now){
ans+=abs(du[now]);
vis[now]=1;
for(int i=head[now];i!=-1;i=b[i].next){
int u=b[i].to;
if(vis[u]==0){
dfs(u);
}
}
}
int main(){
memset(head,-1,sizeof(head));
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n+2;i++){
for(int j=1;j<=m+2;j++){
a[i][j]=++cnt;
}
}
for(int i=1;i<=n;i++){
scanf("%s",s[i]+1);
for(int j=1;j<=m;j++){
if(s[i][j]=='\\'){
ad(a[i][j],a[i+1][j+1],0);
ad(a[i+1][j+1],a[i][j],0);
bb[a[i][j]]=bb[a[i+1][j+1]]=1;
}
if(s[i][j]=='http://www.likecs.com/'){
ad(a[i][j+1],a[i+1][j],0);
ad(a[i+1][j],a[i][j+1],0);
bb[a[i][j+1]]=bb[a[i+1][j]]=1;
}
if(s[i][j]=='X'){
ad(a[i][j+1],a[i+1][j],0);
ad(a[i][j],a[i+1][j+1],0);
ad(a[i+1][j],a[i][j+1],0);
ad(a[i+1][j+1],a[i][j],0);
bb[a[i][j]]=bb[a[i+1][j]]=bb[a[i+1][j+1]]=bb[a[i][j+1]]=1;
}
}
}
for(int i=1;i<=n;i++){
scanf("%s",s[i]+1);
for(int j=1;j<=m;j++){
if(s[i][j]=='\\'){
ad(a[i][j],a[i+1][j+1],1);
ad(a[i+1][j+1],a[i][j],1);
bb[a[i][j]]=bb[a[i+1][j+1]]=1;
}
if(s[i][j]=='http://www.likecs.com/'){
ad(a[i][j+1],a[i+1][j],1);
ad(a[i+1][j],a[i][j+1],1);
bb[a[i][j+1]]=bb[a[i+1][j]]=1;
}
if(s[i][j]=='X'){
ad(a[i][j+1],a[i+1][j],1);
ad(a[i][j],a[i+1][j+1],1);
ad(a[i+1][j],a[i][j+1],1);
ad(a[i+1][j+1],a[i][j],1);
bb[a[i][j]]=bb[a[i+1][j]]=bb[a[i+1][j+1]]=bb[a[i][j+1]]=1;
}
}
}
int mans=0;
for(int i=1;i<=cnt;i++){
if(bb[i] && !vis[i]){
ans=0;
dfs(i);
if(ans==0) mans+=2;
else mans+=ans;
}
}
printf("%d\n",mans/2);
return 0;
}
