82pts求调
  • 板块P1524 十字绣
  • 楼主Tanliu
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/10/19 12:32
  • 上次更新2024/10/19 14:46:55
查看原帖
82pts求调
1088873
Tanliu楼主2024/10/19 12:32
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<map>
#define int long long
using namespace std;
const int N=205;
int n,m,ans;
char ch;
vector<pair<int,int> >h[N][N],g[N][N];
map<pair<pair<int,int>,pair<int,int> >,int>mp1,mp2;
void dfs(int x,int y,int flag){
	if(flag==0){
		for(int i=0;i<g[x][y].size();i++){
			if(mp2[make_pair(make_pair(x,y),g[x][y][i])]==1){
				mp2[make_pair(make_pair(x,y),g[x][y][i])]=0;
				mp2[make_pair(g[x][y][i],make_pair(x,y))]=0;
				dfs(g[x][y][i].first,g[x][y][i].second,1);
			}
		}
	}else{
		for(int i=0;i<h[x][y].size();i++){
			if(mp1[make_pair(make_pair(x,y),h[x][y][i])]==1){
				mp1[make_pair(make_pair(x,y),h[x][y][i])]=0;
				mp1[make_pair(h[x][y][i],make_pair(x,y))]=0;
				dfs(h[x][y][i].first,h[x][y][i].second,0);
			}
		}
	}
}
signed main(){
	scanf("%lld %lld",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>ch;
			if(ch=='\\'||ch=='X'){
				mp1[make_pair(make_pair(i,j),make_pair(i+1,j+1))]=1;
				mp1[make_pair(make_pair(i+1,j+1),make_pair(i,j))]=1;
				h[i][j].push_back(make_pair(i+1,j+1));
				h[i+1][j+1].push_back(make_pair(i,j));
			}
			if(ch=='/'||ch=='X'){
				mp1[make_pair(make_pair(i+1,j),make_pair(i,j+1))]=1;
				mp1[make_pair(make_pair(i,j+1),make_pair(i+1,j))]=1;
				h[i][j+1].push_back(make_pair(i+1,j));
				h[i+1][j].push_back(make_pair(i,j+1));
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>ch;
			if(ch=='\\'||ch=='X'){
				mp2[make_pair(make_pair(i,j),make_pair(i+1,j+1))]=1;
				mp2[make_pair(make_pair(i+1,j+1),make_pair(i,j))]=1;
				g[i][j].push_back(make_pair(i+1,j+1));
				g[i+1][j+1].push_back(make_pair(i,j));
			}
			if(ch=='/'||ch=='X'){
				mp2[make_pair(make_pair(i+1,j),make_pair(i,j+1))]=1;
				mp2[make_pair(make_pair(i,j+1),make_pair(i+1,j))]=1;
				g[i][j+1].push_back(make_pair(i+1,j));
				g[i+1][j].push_back(make_pair(i,j+1));
			}
		}
	}
	for(int i=1;i<=n+1;i++){
		for(int j=1;j<=m+1;j++){
			for(int k=0;k<h[i][j].size();k++){
				if(mp1[make_pair(make_pair(i,j),h[i][j][k])]==1){ans++;
//					printf("H:%lld %lld-->%lld %lld\n",i,j,h[i][j][k].first,h[i][j][k].second);
					mp1[make_pair(make_pair(i,j),h[i][j][k])]=0;
					mp1[make_pair(h[i][j][k],make_pair(i,j))]=0;
					dfs(h[i][j][k].first,h[i][j][k].second,0);
				}
			}
		}
	}
	for(int i=1;i<=n+1;i++){
		for(int j=m+1;j>=1;j--){
			for(int k=0;k<g[i][j].size();k++){
				if(mp2[make_pair(make_pair(i,j),g[i][j][k])]==1){
//					printf("G:%lld %lld-->%lld %lld\n",i,j,g[i][j][k].first,g[i][j][k].second);
					ans++;
					mp2[make_pair(make_pair(i,j),g[i][j][k])]=0;
					mp2[make_pair(g[i][j][k],make_pair(i,j))]=0;
					dfs(g[i][j][k].first,g[i][j][k].second,1);
				}
			}
		}
	}
	printf("%lld",ans);
	return 0;
}
/*
4 5
XXXXX
XXXXX
XXXXX
XXXXX
.....
.....
.....
.....

*/
2024/10/19 12:32
加载中...