网站结构怎么分析,盐山县网站建设公司,移动公司网络维护待遇,90设计官方仔细读题#xff0c;会发现吃掉敌人点对方案数的贡献很神奇。如果走的空格相同#xff0c;而走的敌人点不同#xff0c;对答案无贡献#xff0c;而对于走的空格相同#xff0c;但一种走了敌人点#xff0c;另一种没走#xff0c;算两个方案。。。。sb出题人语文简直是和… 仔细读题会发现吃掉敌人点对方案数的贡献很神奇。如果走的空格相同而走的敌人点不同对答案无贡献而对于走的空格相同但一种走了敌人点另一种没走算两个方案。。。。sb出题人语文简直是和我学的。。。。 可见对于能相互到达的敌人点我们该缩点。也就是说我们对与这一坨敌人点相连的空格互相连上双向边。可以互相到达并把每两个互相到达的空格连上边。 然后跑spfa加一个当dis[i]dis[j]1时ans[i]ans[j]就行了。 注意边不要建多。 ans不用开ll #includecstring
#includecstdlib
#includecstdio
#includealgorithm
#includeiostream
#includequeue
#define ll long long
using namespace std;
inline int read()
{int sum0;char xgetchar();while(x0||x9)xgetchar();while(x0x9){sum(sum1)(sum3)x-0;xgetchar();}return sum;
}
struct node{int x,y;}S,T;
struct road{int v,next;}lu[10000*8];
queuenode q;queueint 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(x0||y0||xn||ym||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);cnt0;memset(hh,0,sizeof(hh));while(!q.empty()){node xq.front();q.pop();for(int i0;i8;i){node to;to.xx.xwz[i][0],to.yx.ywz[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 i1;icnt;i)for(int ji1;jcnt;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 i1;in;i)for(int j1;jm;j)id[i][j]tot;for(int i1;in;i)for(int j1;jm;j)if(!a[i][j])for(int k0;k8;k){int xiwz[k][0],yjwz[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 i1;in;i)for(int j1;jm;j)if(a[i][j]1!vis[i][j]){vis[i][j]1;node x;x.xi,x.yj;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 xQ.front();Q.pop();vis[x]0;for(int iadj[x];i;ilu[i].next){int tolu[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()
{nread();mread();for(int i1;in;i)for(int j1;jm;j){a[i][j]read();if(a[i][j]3)S.xi,S.yj,a[i][j]0;if(a[i][j]4)T.xi,T.yj,a[i][j]0;}init();if(!spfa()){cout-1;return 0;}coutdis[id[T.x][T.y]]-1endlans[id[T.x][T.y]];
} 转载于:https://www.cnblogs.com/QTY2001/p/7632669.html
