前年的省赛题，难点在于这个石头的推移不太好处理
后来还是看了阳神当年的省赛总结，发现这个石头这里，因为就四五个子，就暴力dfs处理即可。先把石头当做普通障碍，进行一遍全图的dfs或者bfs，找到可以找的点，然后dfs每次探索新区域的新点即可，想通了这里很好做了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char mat[15][15];
int vis[15][15];
int rock[8][2],cnt;
int n,m;
int dir[][2]={{1,0},{-1,0},{0,1},{0,-1}};
int inq[8];
int res,sum;
void dfs1(int sx,int sy,int col)
{
vis[sx][sy]=col;
for (int i=0;i<4;i++){
int nx=sx+dir[i][0];
int ny=sy+dir[i][1];
if (nx<0 || nx>=n || ny<0 || ny>=m) continue;
if (vis[nx][ny]) continue;
if (mat[nx][ny]=='O'|| mat[nx][ny]=='X') continue;
if(mat[nx][ny]=='C'){
res++;
}
dfs1(nx,ny,col);
}
}
void back(int x,int y,int col)
{
vis[x][y]=0;
for (int i=0;i<4;i++){
int nx=x+dir[i][0];
int ny=y+dir[i][1];
if (nx<0 || ny<0 || nx>=n || ny>=m) continue;
if (vis[nx][ny]!=col) continue;
back(nx,ny,col);
}
}
int maxn,ans;
void proc(int num)
{
char cc;
if (num>=cnt) return;
for (int i=0;i<cnt;i++){
if (inq[i]) continue;
inq[i]=1;
int x=rock[i][0];
int y=rock[i][1];
for (int j=0;j<4;j++){
int dx=x+dir[j][0];
int dy=y+dir[j][1];
if (dx<0 || dx>=n || dy<0 || dy>=m) continue;
if (mat[dx][dy]=='X') continue;
if (!vis[dx][dy]) continue;
int tx=x-dir[j][0];
int ty=y-dir[j][1];
if (tx<0 || tx>=n || ty<0 || ty>=m) continue;
if (mat[tx][ty]!='.' && !vis[tx][ty]) continue;
cc=mat[tx][ty];
mat[tx][ty]='O';
mat[x][y]='.';
res=0;
dfs1(x,y,i+2);
maxn+=res;
int tmp=res;
ans=max(ans,maxn);
proc(num+1);
back(x,y,i+2);
maxn-=tmp;
mat[tx][ty]=cc;
mat[x][y]='O';
}
proc(num+1);
inq[i]=0;
}
}
int main()
{
int t,sx,sy;
scanf("%d",&t);
while (t--)
{
cnt=0;
scanf("%d%d",&n,&m);
for (int i=0;i<n;i++){
scanf("%s",mat[i]);
for (int j=0;j<m;j++){
vis[i][j]=0;
if (mat[i][j]=='S'){
sx=i;sy=j;mat[i][j]='.';
}
else
if (mat[i][j]=='O'){
rock[cnt][0]=i;
rock[cnt++][1]=j;
}
}
}
res=0;
dfs1(sx,sy,1);
sum=res;
maxn=0,ans=0;
memset(inq,0,sizeof inq);
proc(0);
ans+=sum;
printf("%d\n",ans);
}
return 0;
} 转载于:https://www.cnblogs.com/kkrisen/p/3962917.html