题目链接
题目大意
题目思路
比赛的时候读错题了，以为是总共只能去x一次，后面发现是每个x点只能去一次
后面比赛的时候想的是\(dp[x][y][sta1][sta2]\)
表示现在位于\((x,y)\)节点，且踩了\(sta1\)状态的陷阱，有\(sta2\)状态的宝藏
显然复杂度过大
后面看了题解，其实不需要记录\(x,y\)因为很多点本质上是一样的，只需要记录现在位于哪个特殊节点即可
把起点和“X”和“@”当作结点建图，边为通过“.”能够直接连通的结点。以“当前结点”+“遇到过的结点状态压缩”为状
态DP。
写起来感觉很麻烦，感觉自己写的有点绕
代码
#include<bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int maxn=100+5,inf=0x3f3f3f3f,mod=1e9+7;
const double eps=1e-6;
int n,m;
char s[maxn][maxn];
int mp[maxn][maxn],vis[maxn][maxn];
int ans[30];
int cnt;
int dp[1<<21][22];
vector<int> vec[30],gt[30];
pair<int,int> pa[30];
int dx[]={0,-1,1,0,0};
int dy[]={0,0,0,-1,1};
void init(){// 标号
for(int i=1;i<=20;i++){
ans[i]=0;
gt[i].clear();
}
cnt=1;
for(int j=1;j<=m;j++){// 找出口标记为1
if(s[1][j]=='.'){
mp[1][j]=1;
}
if(s[n][j]=='.'){
mp[n][j]=1;
}
}
for(int i=1;i<=n;i++){
if(s[i][1]=='.'){
mp[i][1]=1;
}
if(s[i][m]=='.'){
mp[i][m]=1;
}
}
//给陷阱和宝藏标号
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(s[i][j]=='X'||s[i][j]=='@'){
mp[i][j]=++cnt;
}
if(s[i][j]=='@'){
ans[cnt]=1;
}
if(mp[i][j]){
pa[mp[i][j]]={i,j};
}
}
}
for(int i=1;i<=n;i++){ // 标记每个点能领到什么宝藏
for(int j=1;j<=m;j++){
if(mp[i][j]==0) continue;
for(int k=0;k<=4;k++){
int nx=i+dx[k];
int ny=j+dy[k];
if(nx<1||nx>n||ny<1||ny>m){
continue;
}
if(s[nx][ny]=='@'){ // 放进去之后就不走了
gt[mp[i][j]].push_back(mp[nx][ny]);
}
}
}
}
}
void bfs(int id,int x,int y){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
vis[i][j]=0;
}
}
queue<pair<int,int> > que;
que.push({x,y});
vis[x][y]=1;
while(!que.empty()){
pii now=que.front();
que.pop();
for(int i=1;i<=4;i++){
int nx=now.fi+dx[i];
int ny=now.se+dy[i];
if(nx<1||nx>n||ny<1||ny>m||vis[nx][ny]||s[nx][ny]=='#'){
continue;
}
vis[nx][ny]=1;
if(mp[nx][ny]){ // 放进去之后就不走了
vec[id].push_back(mp[nx][ny]);
}else{
que.push({nx,ny});
}
}
}
}
int cal(int x){
int cnt=0;
while(x){
if(x&1) cnt++;
x/=2;
}
return cnt;
}
signed main(){
while(scanf("%d%d",&n,&m)!=-1){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf(" %c",&s[i][j]);
mp[i][j]=0;
}
}
init();
for(int i=1;i<=cnt;i++){
vec[i].clear();
bfs(i,pa[i].fi,pa[i].se);
}
for(int sta=1;sta<(1<<cnt);sta++){
for(int now=0;now<cnt;now++){
dp[sta][now]=0;
}
}
dp[1][0]=1;
for(int sta=1;sta<(1<<cnt);sta++){
for(int now=0;now<cnt;now++){
if(dp[sta][now]==0) continue;
for(auto x:vec[now+1]){
int nxt=x-1;
// 如果走过并且是x点，则不再走
if((sta&(1<<nxt))&&s[pa[x].fi][pa[x].se]=='X') continue;
dp[sta|(1<<nxt)][nxt]=1;
}
}
}
int pr=0;
for(int sta=1;sta<(1<<cnt);sta++){
if(dp[sta][0]==0) continue;
int tmp=0;
int now=0;
for(int j=1;j<=cnt;j++){
if(sta&(1<<(j-1))){
for(auto x:gt[j]){
now|=(1<<x);
}
}
}
pr=max(pr,cal(now));
}
printf("%d\n",pr);
}
return 0;
}
// 3 1 3 2