题面解释：

地图寻宝，起点 $\texttt S$ 在一个点集中但不知道具体是哪个点，不进 $\texttt X$ 的情况下最大化所经 $\texttt o$ 的数量。

思路分析：

下文 $k$ 指 $S$ 个数。

$k=1$ 怎么做？直接 bfs，类似洪水填充得出可达格，计算 $\texttt o$ 数量。如果没有任何视野怎么做？即我们永远不知道在哪个起点，只能走对于所有起点都安全的点。结合数据范围提示我们状压，bfs 时传入一个状态 $s$，表示此时可能起点的集合。

一个基本策略：如果在通过已知信息筛选出的可以是当前起点的 $\texttt S$ 中存在起点使某个 $\texttt .$ 实际上是 $\texttt X$，不能走；反之，这个点一定安全，必走。为什么必走？因为走了这个点虽然不会获得 $\texttt o$，但是可以扩大视野，限制起点的选择，显然不劣。

这是有一个 $O(2^knm)$ 的做法，然后发现事实上最多就是对每个点遍历一遍，是 $O(knm)$ 的，也就是很多状态 $s$ 是不可能出现的，只需要将有包含关系的状态的信息递归传递一下即可，注意一定是最坏情况所以对子状态取 $\min$。

还有一个问题就是根据已知视野筛选起点，这个怎么做到 $O(knm)$ 呢？既然我们都对合法起点状压了，不难想到对地图信息也状压，暴力枚举位运算判断即可。

AC Code:

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
using i64=long long;
const int nx[]={0,0,1,-1,1,1,-1,-1};
const int ny[]={1,-1,0,0,1,-1,1,-1};
const int k=405,N=820;
struct Point{int x,y;};
int n,m;
i64 bk[N][N],t[N][N][3];
char mp[N][N];
bool vis[N][N];
int bfs(i64 s){
	queue<Point>q;q.push({k,k});
	memset(vis,0,sizeof(vis));
	vis[k][k]=1;
	//遍历当前状态所有安全格
	while(!q.empty()){
		Point u=q.front();q.pop();
		for(int o=0;o<4;o++){
			Point v={u.x+nx[o],u.y+ny[o]};
			if(!vis[v.x][v.y]&&(bk[v.x][v.y]&s)==s)
				vis[v.x][v.y]=1,q.push({v.x,v.y});
		}
	}
	//枚举判断视野是否能划分起点状态
	for(int x=1;x<=k*2;x++)
		for(int y=1;y<=k*2;y++)
			for(int o=0;o<8;o++)if(vis[x+nx[o]][y+ny[o]]){
				for(int id=0;id<3;id++){
					//判断s中所有起点当前视野是否都是/都不是id
					//对于分支情况考虑最坏，取min
                	i64 s1=t[x][y][id]&s,s2=s1^s;
					if(s1!=s&&s2!=s)return min(bfs(s1),bfs(s2));
            	}break;
			}
	int ans=0;
	for(int x=1;x<=k*2;x++)
		for(int y=1;y<=k*2;y++)
			vis[x][y]&&(t[x][y][1]&s)&&ans++;
	return ans;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
	cin>>n>>m;
	vector<Point>g;
	for(int x=1;x<=n;x++)
		for(int y=1;y<=m;y++){
			cin>>mp[x+k][y+k];
			if(mp[x+k][y+k]=='S')g.pb({x,y});
		}
	for(int o=0;o<g.size();o++)
		for(int x=1;x<=k*2;x++)
			for(int y=1;y<=k*2;y++){
				//注意不同起点相对位置不同
				char ch=mp[x+g[o].x][y+g[o].y];
				//bk表示这格关于那些起点安全
				if(ch=='.'||ch=='o'||ch=='S')bk[x][y]|=(1ll<<o);
				//t表示对视野信息的状压，用于判断合法起点
				if(ch=='#')t[x][y][0]|=(1ll<<o);
				else if(ch=='o')t[x][y][1]|=(1ll<<o);
				else t[x][y][2]|=(1ll<<o);
			}
	cout<<bfs((1ll<<g.size())-1);
	return 0;
}

完结撒花！！！