首页 > 代码库 > bfs CCF2016第七次 游戏
bfs CCF2016第七次 游戏
1 // bfs CCF2016第七次 游戏 2 // 思路: 3 // O(300*100*100) 4 // 直接暴搜 5 // 注意,同一格同一时间不能经过两次!!! 6 7 #include <bits/stdc++.h> 8 using namespace std; 9 #define LL long long10 const double inf = 123456789012345.0;11 const LL MOD =100000000LL;12 const int N =1e4+10;13 #define clc(a,b) memset(a,b,sizeof(a))14 const double eps = 1e-7;15 void fre() {freopen("in.txt","r",stdin);}16 void freout() {freopen("out.txt","w",stdout);}17 inline int read() {int x=0,f=1;char ch=getchar();while(ch>‘9‘||ch<‘0‘) {if(ch==‘-‘) f=-1; ch=getchar();}while(ch>=‘0‘&&ch<=‘9‘) {x=x*10+ch-‘0‘;ch=getchar();}return x*f;}18 19 int d[4][2]={{-1,0},{1,0},{0,-1},{0,1}};20 struct node{21 int inx;22 int r,c,a,b;23 }g[N];24 25 bool vis[110][110][300]={0};26 void init(int n,int m){27 for(int i=1;i<=n;i++){28 for(int j=1;j<=m;j++){29 g[(i-1)*m+j].r=i;30 g[(i-1)*m+j].c=j;31 g[(i-1)*m+j].a=g[(i-1)*m+j].b=g[(i-1)*m+j].inx=0;32 }33 }34 }35 36 queue<node> q;37 int bfs(int n,int m){38 q.push(g[1]);39 int ans=0;40 while(!q.empty()){41 node tem=q.front();42 q.pop();43 ans=tem.inx;44 if(tem.r==n&&tem.c==m){45 return ans;46 }47 ans++;48 for(int i=0;i<4;i++){49 int x=tem.r+d[i][0];50 int y=tem.c+d[i][1];51 int num=(x-1)*m+y;52 if(x>=1&&x<=n&&y>=1&&y<=m&&(ans>g[num].b||ans<g[num].a)&&ans<=300&&!vis[x][y][ans]){53 node tm;54 tm=g[num];55 tm.inx=ans;56 vis[x][y][ans]=true;57 q.push(tm);58 }59 }60 }61 }62 63 int main(){64 // fre();65 int n,m,t;66 scanf("%d%d%d",&n,&m,&t);67 init(n,m);68 for(int i=1;i<=t;i++){69 int r,c,a,b;70 scanf("%d%d%d%d",&r,&c,&a,&b);71 g[(r-1)*m+c].a=a;72 g[(r-1)*m+c].b=b;73 }74 int ans=bfs(n,m);75 printf("%d\n",ans);76 return 0;77 }
bfs CCF2016第七次 游戏
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。