自动搬运

查看原文

来自洛谷，原作者为

	MoonCake2011 有朋自远方来，板砖呼，左手呼完右手呼，呼不S再呼||题目很少，很快就做完了。微笑着做完，才会胜利。||原 Libingyue2011||J:400->360->280 S:265->258

搬运于2025-08-24 21:27:45，当前版本为作者最后更新于2023-08-02 21:54:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我们用 dfs 找连通块。

每次将选过的坐标进行扩散，所以我们要记录每次选过的坐标。

选了 $7$ 格后，将那 $7$ 个坐标的 hash 值存入数组里。

对那个数组去重。

最终那个数组里的非重复个数就是答案。

记得用 vis 数组标记。

竟然能在 150ms 内卡过，时间总和才不到 710ms。

代码。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int d[4][2]={{0,1},{-1,0},{0,-1},{1,0}};
bool vis[10][10];
char a[10][10];
bool check(int x,int y){
	return (x>0 && y>0 && x<=5 && y<=5);
}
vector<pair<int,int> >v;
struct node{
	pair<int,int>a[9];
	node(){
		for(int i=0;i<7;i++)
			a[i].first=a[i].second=0;
	}
	pair<int,int> &operator [] (int i){
		return a[i];
	}
	void Sort(){
		std::sort(a,a+7);
	}
	int get_hash(){
		int base=7,ans=0;
		for(int i=0;i<7;i++){
			ans=ans*base+a[i].first;
			ans=ans*base+a[i].second;
		}
		return ans;
	}
};
vector<int>ans;
void dfs(int x,int y,int cnt,int p){
	v.push_back({x,y});
	if(p==7){
		if(cnt>3){
			node x=node();
			for(int i=0;i<7;i++)
				x[i]=v[i];
			x.Sort();
			ans.push_back(x.get_hash());
		}
		v.pop_back();
		return;
	}
	vis[x][y]=1;
	for(int i=0;i<v.size();i++){
		int ux=v[i].first,uy=v[i].second;
		for(int j=0;j<4;j++){
			int tx=ux+d[j][0],ty=uy+d[j][1];
			if(!vis[tx][ty] && check(tx,ty))
				dfs(tx,ty,cnt+(a[tx][ty]=='J'),p+1);
		}
	}
	v.pop_back();
	vis[x][y]=0;
}
void read(){
	for(int i=1;i<=5;i++)
		for(int j=1;j<=5;j++)
			cin>>a[i][j];
}
signed main() {
	read();
	for(int i=1;i<=5;i++)
		for(int j=1;j<=5;j++)
			dfs(i,j,a[i][j]=='J',1);
	sort(ans.begin(),ans.end());
	int p=unique(ans.begin(),ans.end())-ans.begin();
	cout<<p;
	return 0;
}