USACO maze1

发布时间:2016-12-6 8:55:32 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"USACO maze1",主要涉及到USACO maze1方面的内容,对于USACO maze1感兴趣的同学可以参考一下。

放在最短路这一章有一点坑人 第一个想法:Dijkstra 发现是无向图 然后想:拓扑排序 发现是无权图 无向无权图的SP应该用BFS即可解决 /* ID: 13917981 PROG: maze1 LANG: C++ */ #include <iostream> #include <cstdio> #include <cstring> #include <string> #include <ctime> #include <vector> #include <list> #include <deque> #include <queue> #include <stack> #include <map> #include <set> #include <algorithm> #include <cmath> #define REP(i,n) for(int i=0;i<(n);i++) #define REP1(i,n) for(int i=1;i<=(n);i++) #define FOR(i,a,b) for(int i=(a);i<=(b);i++) #define CLR(x,n) memset(x,n,sizeof(x)) #define PN printf("\n") #define read(x) scanf("%d",&x) #define read2(x,y) scanf("%d%d",&x,&y) #define read3(x,y,z) scanf("%d%d%d",&x,&y,&z) #define write(x) printf("%d",x) #define write1(x) printf("%d ",x) #define writeln(x) printf("%d\n",x) #define write2(x,y) printf("%d %d",x,y) #define writeln2(x,y) printf("%d %d\n",x,y) #define write3(x,y,z) printf("%d %d %d",x,y,z) #define writeln3(x,y,z) printf("%d %d %d\n",x,y,z) using namespace std; void setio(string name) { string in_f=name+".in"; string out_f=name+".out"; freopen(in_f.c_str(),"r",stdin); freopen(out_f.c_str(),"w",stdout); } char readchar(){ char c; do c=getchar();while (!(c==' '||c=='|'||c=='+'|| c=='-')); return c; } struct point{int x,y;}; int h,w; char s[300][300]; int d[2][300][300],vis[300][300]; queue <point>q; void find1(int &x1,int &y1,int &x2,int &y2){ int first=1; REP(j,2*w+1){ if (s[0][j]==' ') if (first){first=0;x1=0;y1=j;} else {x2=0;y2=j;} if (s[2*h][j]==' ') if (first){first=0;x1=2*h;y1=j;} else {x2=2*h;y2=j;} } REP1(i,2*h-1){ if (s[i][0]==' ') if (first){first=0;x1=i;y1=0;} else {x2=i;y2=0;} if (s[i][2*w]==' ') if (first){first=0;x1=i;y1=2*w;} else {x2=i;y2=2*w;} } } bool inrang(int x,int y) {return x>=0 && x<=2*h && y>=0 && y<=2*w;} void bfs(int ty,int x,int y){ CLR(vis,0);point p,p1; if (d[ty][x-1][y]!=-1 && inrang(x-1,y)) {p.x=x-1;p.y=y;} else if (d[ty][x+1][y]!=-1 && inrang(x+1,y)) {p.x=x+1;p.y=y;} else if (d[ty][x][y+1]!=-1 && inrang(x,y+1)) {p.x=x;p.y=y+1;} else if (d[ty][x][y-1]!=-1 && inrang(x,y-1)) {p.x=x;p.y=y-1;} q.push(p);vis[p.x][p.y]=1; d[ty][p.x][p.y]=1; while (!q.empty()){ p=q.front();q.pop(); //writeln2(p.x,p.y); int x0=p.x,y0=p.y; if (d[ty][x0-1][y0]!=-1 && vis[x0-2][y0]==0 && inrang(x0-2,y0)){ vis[x0-2][y0]=1; d[ty][x0-2][y0]=d[ty][x0][y0]+1; p1.x=x0-2;p1.y=y0; q.push(p1); } if (d[ty][x0+1][y0]!=-1 && vis[x0+2][y0]==0 && inrang(x0+2,y0)){ vis[x0+2][y0]=1; d[ty][x0+2][y0]=d[ty][x0][y0]+1; p1.x=x0+2;p1.y=y0; q.push(p1); } if (d[ty][x0][y0-1]!=-1 && vis[x0][y0-2]==0 && inrang(x0,y0-2)){ vis[x0][y0-2]=1; d[ty][x0][y0-2]=d[ty][x0][y0]+1; p1.x=x0;p1.y=y0-2; q.push(p1); } if (d[ty][x0][y0+1]!=-1 && vis[x0][y0+2]==0 && inrang(x0,y0+2)){ vis[x0][y0+2]=1; d[ty][x0][y0+2]=d[ty][x0][y0]+1; p1.x=x0;p1.y=y0+2; q.push(p1); } } } int main() { setio("maze1"); CLR(d,0); read2(w,h); REP(i,2*h+1) REP(j,2*w+1){ s[i][j]=readchar(); if (s[i][j]!=' '){d[0][i][j]=-1;d[1][i][j]=-1;} } int x1,y1,x2,y2; find1(x1,y1,x2,y2);//printf("%d %d %d %d\n",x1,y1,x2,y2); //REP(i,2*h+1){REP(j,2*w+1) //printf("%d\t",d[0][i][j]);PN;} bfs(0,x1,y1); bfs(1,x2,y2); int ans=0; REP(i,2*h+1)REP(j,2*w+1)if (d[0][i][j]!=-1) ans=max( ans, min( d[0][i][j],d[1][i][j] ) ); writeln(ans); //REP(i,2*h+1){REP(j,2*w+1) //putchar(s[i][j]);PN;} //REP(i,2*h+1){REP(j,2*w+1) //printf("%d\t",d[0][i][j]);PN;} PN; //REP(i,2*h+1){REP(j,2*w+1) //printf("%d\t",d[1][i][j]);PN;} //system("pause"); }

上一篇:Oracle日期、字符串格式化函数,位数不足前面加0,一位数字显示两位,格式化数字为定长
下一篇:

相关文章

关键词: USACO maze1

相关评论