算法：IDA*

分數：0

damn it!

Ac_code走丟了~~（主要是沒有寫出來）~~

算法：雙向DFS或者DFS剪枝

分數：0

Ac_code:

#include<bits/stdc++.h>
using namespace std;
int n,m,a[35],ans=INT_MAX;
unordered_map<int,int> mp;
//乘以2以避免除以2的問題
void dfs1(int step,int sum,int num){//從起始條件進行DFS（劈第1~n/2個瓜）
//step:劈到了第幾個瓜、sum:劈了多少斤的瓜、num:劈了幾個瓜if(step==n/2+1){if(mp.count(sum))mp[sum]=min(num,mp[sum]);//保證答案最優else mp[sum]=num;//記錄答案return;}if(sum>m*2) return;//如果那的瓜過多，那就退出dfs1(step+1,sum+a[step]*2,num);//不劈直接拿dfs1(step+1,sum+a[step],num+1);//批了拿一半dfs1(step+1,sum,num);//不劈不拿
}
void dfs2(int step,int sum,int num){//從最終條件進行DFS（劈第n/2+1~n個瓜）if(mp.count(m*2-sum)!=0/*兩邊的DFS的和可行就紀錄*/)ans=min(ans,num+mp[m*2-sum]);//答案可行就記錄if(step==n+1/*如果打算劈n+1個瓜時退出*/||num>ans/*如果答案不夠優就不再進行*/)return;dfs2(step+1,sum+a[step]*2,num);//不劈直接拿dfs2(step+1,sum+a[step],num+1);//批了拿一半dfs2(step+1,sum,num);//不劈不拿
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];sort(a+1,a+n+1);dfs1(1,0,0);//從起始條件進行DFS（劈第1~n/2個瓜）dfs2(n/2+1,0,0);//從最終條件進行DFS（劈第n/2+1~n個瓜）if(ans==INT_MAX)cout<<"Huaqiang is about to strike you !";else cout<<ans;return 0;
}

算法：BFS優化

分數：0

Ac_code:

#include<bits/stdc++.h>
using namespace std;
struct node {int x,y;int t;int l;//是否擁有舉世無雙HJM很劍 
} st,ed;
bool operator <(node x,node y) {return x.t>y.t;
}
priority_queue<node>q;
int n,m;
char a[1005][1005];
int dx[5]= {0,0,0,1,-1};
int dy[5]= {0,1,-1,0,0};
int vis[1005][1005][2];
int chuan[2];
void check(node v){if(vis[v.x][v.y][v.l]>v.t){//保證出現在隊列過的是最優解 vis[v.x][v.y][v.l]=v.t; q.push(v);//放入隊列 }
}
void jian(node v){if(chuan[v.l])	return ;chuan[v.l]=1;//在有舉世無雙HJM很劍和沒舉世無雙HJM很劍時，只要傳送一次就是最優的 v.t+=1;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) {if(a[i][j]!='X') continue;//不是間隙就不傳送check({i,j,v.t,v.l});//如果是間隙，那檢查傳送時是否最優 }}
}
int bfs() {q.push({st.x,st.y,0,0});while(!q.empty()) {node t=q.top();q.pop();if(t.x==ed.x&&t.y==ed.y)	return t.t;//到達祭臺 for(int i=1; i<=4; i++) {int nx=dx[i]+t.x;int ny=dy[i]+t.y;//向四個方向擴展 if(nx<1||ny<1||nx>n||ny>m)	continue;//判斷是否出界node v=t;v.x=nx,v.y=ny;char ta=a[nx][ny];if(ta=='0'){//空地 v.t+=1;check(v);}else if(ta=='1'){//墻 if(v.l==1){//有劍a[nx][ny]=0;v.t+=1;check(v);}	}else if(ta=='2'){//Ultra怪(不用考慮是否會再生)if(v.l==1)	v.t+=1;else v.t+=3;check(v);}else if(ta=='3'){//Super怪 if(v.l==1)	v.t+=1;else v.t+=11;check(v);}else if(ta=='4'){//舉世無雙HJM很劍 v.t+=1;check(v);if(!v.l) v.l=1,v.t+=4;check(v);}else if(ta=='5'){//棧道 if(v.l==0){v.t+=1;check(v);}}else if(ta=='X'){//間隙 v.t+=1;check(v);jian(v);}}}return -1;}
void solve() {while(!q.empty())	q.pop();//清空隊列memset(vis,0,sizeof vis);memset(a,0,sizeof a);memset(chuan,0,sizeof chuan);memset(vis,0x3f,sizeof vis);//求最小值，故memset為0x3f3f3f3f//多測不清空，親人兩行淚 cin>>n>>m;for(int i=1; i<=n; i++) {char ch=getchar();for(int j=1; j<=m; j++) {a[i][j]=getchar();if(a[i][j]=='S')	st.x=i,st.y=j,a[i][j]='0';//起點可多次經過 else if(a[i][j]=='E')	ed.x=i,ed.y=j,a[i][j]='0'; }}int tmp=bfs();if(tmp!=-1)	cout<<tmp<<endl; else cout<<"Maybe Next Time"<<endl;
}
int main(){int T;cin>>T;while(T--)		solve();return 0;
}

算法：DFS剪枝

分數：33（騙的）

Ac_code走丟啦（主要是寫不出來）