仔細(xì)讀題，會(huì)發(fā)現(xiàn)吃掉敵人點(diǎn)對(duì)方案數(shù)的貢獻(xiàn)很神奇。如果走的空格相同，而走的敵人點(diǎn)不同，對(duì)答案無(wú)貢獻(xiàn)，而對(duì)于走的空格相同，但一種走了敵人點(diǎn)，另一種沒(méi)走，算兩個(gè)方案。。。。sb出題人語(yǔ)文簡(jiǎn)直是和我學(xué)的。。。。
可見(jiàn)對(duì)于能相互到達(dá)的敵人點(diǎn)我們?cè)摽s點(diǎn)。也就是說(shuō)，我們對(duì)與這一坨敵人點(diǎn)相連的空格互相連上雙向邊。（可以互相到達(dá)），并把每?jī)蓚€(gè)互相到達(dá)的空格連上邊。
然后跑spfa，加一個(gè)當(dāng)dis[i]==dis[j]+1時(shí)，ans[i]+=ans[j]，就行了。
注意，邊不要建多。
ans不用開(kāi)ll

#include<cstring> #include<cstdlib> #include<cstdio> #include<algorithm> #include<iostream> #include<queue> #define ll long long using namespace std; inline int read() {int sum=0;char x=getchar();while(x<'0'||x>'9')x=getchar();while(x>='0'&&x<='9'){sum=(sum<<1)+(sum<<3)+x-'0';x=getchar();}return sum; } struct node{int x,y;}S,T; struct road{int v,next;}lu[10000*8]; queue<node> q;queue<int> Q; int n,m,tot,cnt,e; int dis[55*55],v[55*55],adj[55*55],al[55*55][55*55]; int vis[55][55],a[55][55],id[55][55],hh[55][55]; ll ans[55*55]; int wz[10][2]={2,1,2,-1,-2,1,-2,-1,1,2,1,-2,-1,2,-1,-2}; inline bool check(int x,int y){if(x<=0||y<=0||x>n||y>m||a[x][y]==2)return 0;return 1;} inline void add(int u,int v){lu[++e]=(road){v,adj[u]};adj[u]=e;} void get(node aaa) {q.push(aaa);cnt=0;memset(hh,0,sizeof(hh));while(!q.empty()){node x=q.front();q.pop();for(int i=0;i<8;i++){node to;to.x=x.x+wz[i][0],to.y=x.y+wz[i][1];if(!check(to.x,to.y))continue;if(a[to.x][to.y]==1&&!vis[to.x][to.y]){q.push(to);vis[to.x][to.y]=1;}if(a[to.x][to.y]==0&&!hh[to.x][to.y]){v[++cnt]=id[to.x][to.y];hh[to.x][to.y]=1;}}}for(int i=1;i<=cnt;i++)for(int j=i+1;j<=cnt;j++)if(!al[v[i]][v[j]])add(v[i],v[j]),add(v[j],v[i]),al[v[i]][v[j]]=al[v[j]][v[i]]=1; } void init() {for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)id[i][j]=++tot;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(!a[i][j])for(int k=0;k<8;k++){int x=i+wz[k][0],y=j+wz[k][1];if(!check(x,y)||a[x][y]!=0)continue;add(id[i][j],id[x][y]);//add(id[x][y],id[i][j]);}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(a[i][j]==1&&!vis[i][j]){vis[i][j]=1;node x;x.x=i,x.y=j;get(x);} } bool spfa() {int vis[55*55];memset(vis,0,sizeof(vis));memset(dis,40,sizeof(dis));Q.push(id[S.x][S.y]);dis[id[S.x][S.y]]=0;ans[id[S.x][S.y]]=vis[id[S.x][S.y]]=1;while(!Q.empty()){int x=Q.front();Q.pop();vis[x]=0;for(int i=adj[x];i;i=lu[i].next){int to=lu[i].v;if(dis[to]>dis[x]+1){dis[to]=dis[x]+1;ans[to]=ans[x];if(!vis[to]){vis[to]=1;Q.push(to);}}else if(dis[to]==dis[x]+1){ans[to]+=ans[x];if(!vis[to]){vis[to]=1;Q.push(to);}}}}return dis[id[T.x][T.y]]<100000; } int main() {n=read();m=read();for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){a[i][j]=read();if(a[i][j]==3)S.x=i,S.y=j,a[i][j]=0;if(a[i][j]==4)T.x=i,T.y=j,a[i][j]=0;}init();if(!spfa()){cout<<-1;return 0;}cout<<dis[id[T.x][T.y]]-1<<endl<<ans[id[T.x][T.y]]; }

轉(zhuǎn)載于:https://www.cnblogs.com/QTY2001/p/7632669.html

總結(jié)

以上是生活随笔為你收集整理的大暴搜 chess的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。