首页 > 代码库 > 首师大附中科创教育平台 我的刷题记录 0284 最强大脑
首师大附中科创教育平台 我的刷题记录 0284 最强大脑
从现在开始，我的刷题记录都开始给大家一个一个刷！今天给大家献上“E”级题：最强大脑！！
| ||||||||||||||
|
好的，以上就是最强大脑的题目要求，现在献上代码！！！当当当！！！
#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>#include<queue>#include<cstring>#define INF 2147483647using namespace std;inline int read(){ int x=0,t=1,c; while(!isdigit(c=getchar()))if(c==‘-‘)t=-1; while(isdigit(c))x=x*10+c-‘0‘,c=getchar(); return x*t;}bool is_in(int left,int down,int right,int up,int x,int y,int r){ if(left>right||down<up)return false; int X,Y,distx,disty; if(x<left)X=0; else if(x>=left&&x<=right)X=1; else if(x>right)X=2; if(y<up)Y=0; else if(y>=up&&y<=down)Y=1; else if(y>down)Y=2; if(X==0) { if(Y==0) { distx=left-x; disty=up-y; if(distx+disty<=r)return true; else return false; } if(Y==1) { if(left-x<=r)return true; else return false; } if(Y==2) { distx=left-x; disty=y-down; if(distx+disty<=r)return true; else return false; } } if(X==1) { if(Y==0) { if(up-y<=r)return true; else return false; } if(Y==1) { return true; } if(Y==2) { if(y-down<=r)return true; else return false; } } if(X==2) { if(Y==0) { distx=x-right; disty=up-y; if(distx+disty<=r)return true; else return false; } if(Y==1) { if(x-right<=r)return true; else return false; } if(Y==2) { distx=x-right; disty=y-down; if(distx+disty<=r)return true; else return false; } }}bool is_all_in(int left,int down,int right,int up,int x,int y,int r){ if(left>right||down<up)return false; int distx,disty; distx=abs(left-x); disty=abs(down-y); if(distx+disty>r)return false; disty=abs(y-up); if(distx+disty>r)return false; distx=abs(x-right); disty=abs(down-y); if(distx+disty>r)return false; disty=abs(y-up); if(distx+disty>r)return false; return true;}int first[140000],target[10000000],next[10000000],value[10000000],countn=1;void AddEdge(int u,int v,int length){ target[countn]=v; value[countn]=length; next[countn]=first[u]; first[u]=countn++;}int from,posx,posy,r,v,A[160][160],B[160][160];void build(int o,int left,int down,int right,int up,bool cut){ if(left==right&&up==down)return; int lc=o<<1,rc=lc+1,m; AddEdge(o,lc,0); AddEdge(o,rc,0); if((cut||left==right)&&up!=down) { m=up+down>>1; build(lc,left,m,right,up,!cut); build(rc,left,down,right,m+1,!cut); } else { m=left+right>>1; build(lc,left,down,m,up,!cut); build(rc,m+1,down,right,up,!cut); }}void update(int o,int left,int down,int right,int up,bool cut){ if(is_all_in(left,down,right,up,posx,posy,r)) { AddEdge(from,o,v); return; } int lc=o<<1,rc=lc+1,m; if((cut||left==right)&&up!=down) { m=up+down>>1; if(is_in(left,m,right,up,posx,posy,r))update(lc,left,m,right,up,!cut); if(is_in(left,down,right,m+1,posx,posy,r))update(rc,left,down,right,m+1,!cut); } else { m=left+right>>1; if(is_in(left,down,m,up,posx,posy,r))update(lc,left,down,m,up,!cut); if(is_in(m+1,down,right,up,posx,posy,r))update(rc,m+1,down,right,up,!cut); }}int query(int o,int left,int down,int right,int up,bool cut){ if(left==right&&up==down)return o; int lc=o<<1,rc=lc+1,m; if((cut||left==right)&&up!=down) { m=up+down>>1; if(posy<=m)return query(lc,left,m,right,up,!cut); else return query(rc,left,down,right,m+1,!cut); } else { m=left+right>>1; if(posx<=m)return query(lc,left,down,m,up,!cut); else return query(rc,m+1,down,right,up,!cut); }}struct State{ int pos,cost; bool operator < (const State &b)const { return cost>b.cost; }}take,put;priority_queue<State> PQ;int fastest[140000],N,M;int Dijkstra(int x0,int y0,int x1,int y1){ memset(fastest,127,sizeof(fastest)); while(!PQ.empty())PQ.pop(); int s,t; posx=x0; posy=y0; s=query(1,1,N,M,1,0); posx=x1; posy=y1; t=query(1,1,N,M,1,0); put.pos=s; put.cost=0; PQ.push(put); while(!PQ.empty()) { take=PQ.top(); PQ.pop(); if(fastest[take.pos]<take.cost)continue; if(take.pos==t) { return take.cost; } for(int i=first[take.pos];i;i=next[i]) { if(fastest[target[i]]>take.cost+value[i]) { fastest[target[i]]=take.cost+value[i]; put.pos=target[i]; put.cost=fastest[put.pos]; PQ.push(put); } } } return -1;}int main(){ N=read(),M=read(); build(1,1,N,M,1,0); for(int i=1;i<=N;i++) { for(int j=1;j<=M;j++) { B[i][j]=read(); } } for(int i=1;i<=N;i++) { for(int j=1;j<=M;j++) { A[i][j]=read(); if(B[i][j]) { posx=j; posy=i; r=B[i][j]; v=A[i][j]; from=query(1,1,N,M,1,0); update(1,1,N,M,1,0); } } } int y0=read(),x0=read(),y1=read(),x1=read(),y2=read(),x2=read(); int XtoY,YtoX,XtoZ,ZtoX,YtoZ,ZtoY,ans=INF; char place=‘N‘; XtoY=Dijkstra(x0,y0,x1,y1); YtoX=Dijkstra(x1,y1,x0,y0); XtoZ=Dijkstra(x0,y0,x2,y2); ZtoX=Dijkstra(x2,y2,x0,y0); YtoZ=Dijkstra(x1,y1,x2,y2); ZtoY=Dijkstra(x2,y2,x1,y1); if(~YtoX&&~ZtoX) { if(YtoX+ZtoX<ans) { place=‘X‘; ans=YtoX+ZtoX; } } if(~ZtoY&&~XtoY) { if(ZtoY+XtoY<ans) { place=‘Y‘; ans=XtoY+ZtoY; } } if(~XtoZ&&~YtoZ) { if(XtoZ+YtoZ<ans) { place=‘Z‘; ans=XtoZ+YtoZ; } } if(place==‘N‘)puts("NO"); else printf("%c\n%d",place,ans);}
首师大附中科创教育平台 我的刷题记录 0284 最强大脑
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。