bfs CCF2016第七次 游戏

 // bfs CCF2016第七次 游戏
// 思路:
// O(300*100*100)
// 直接暴搜
// 注意,同一格同一时间不能经过两次!!! #include <bits/stdc++.h>
using namespace std;
#define LL long long
const double inf = 123456789012345.0;
const LL MOD =100000000LL;
const int N =1e4+;
#define clc(a,b) memset(a,b,sizeof(a))
const double eps = 1e-;
void fre() {freopen("in.txt","r",stdin);}
void freout() {freopen("out.txt","w",stdout);}
inline int read() {int x=,f=;char ch=getchar();while(ch>''||ch<'') {if(ch=='-') f=-; ch=getchar();}while(ch>=''&&ch<='') {x=x*+ch-'';ch=getchar();}return x*f;} int d[][]={{-,},{,},{,-},{,}};
struct node{
int inx;
int r,c,a,b;
}g[N]; bool vis[][][]={};
void init(int n,int m){
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
g[(i-)*m+j].r=i;
g[(i-)*m+j].c=j;
g[(i-)*m+j].a=g[(i-)*m+j].b=g[(i-)*m+j].inx=;
}
}
} queue<node> q;
int bfs(int n,int m){
q.push(g[]);
int ans=;
while(!q.empty()){
node tem=q.front();
q.pop();
ans=tem.inx;
if(tem.r==n&&tem.c==m){
return ans;
}
ans++;
for(int i=;i<;i++){
int x=tem.r+d[i][];
int y=tem.c+d[i][];
int num=(x-)*m+y;
if(x>=&&x<=n&&y>=&&y<=m&&(ans>g[num].b||ans<g[num].a)&&ans<=&&!vis[x][y][ans]){
node tm;
tm=g[num];
tm.inx=ans;
vis[x][y][ans]=true;
q.push(tm);
}
}
}
} int main(){
// fre();
int n,m,t;
scanf("%d%d%d",&n,&m,&t);
init(n,m);
for(int i=;i<=t;i++){
int r,c,a,b;
scanf("%d%d%d%d",&r,&c,&a,&b);
g[(r-)*m+c].a=a;
g[(r-)*m+c].b=b;
}
int ans=bfs(n,m);
printf("%d\n",ans);
return ;
}
上一篇:Python学习-12.Python的输入输出


下一篇:WebMethod 属性