【POJ 2049】Finding Nemo
迷宫类Bfs，不同于之前的是之前是点 这次是房间，我的做法是把每个房间看做一个点(移动地图使房间为整型坐标 便于用数组下表表示房间坐标) 上下左右是墙/门/无用1 0 -1表示 然后Bfs遍历即可 坑点有x/y<0 和x/y > 199的情况 贡献了好多个RE
上代码
;typedef struct Point{int d[4];//0-上 1-下 2-左 3-右int st;}Point;int dirx[] = { 0, 0,-1, 1};int diry[] = { 1,-1, 0, 0};Point mp[233][233];bool rest[233][233];bool vis[233][233];int m,n;void Init(){memset(rest,0,sizeof(rest));memset(vis,0,sizeof(vis));}void SetWall(){int x,y,d,t;while(m–){scanf(“%d %d %d %d”,&x,&y,&d,&t);while(t–){if(d){++y;mp[x][y].d[3] = 1;mp[x+1][y].d[2] = 1;if(!rest[x][y]){rest[x][y] = 1;mp[x][y].d[2] = mp[x][y].d[0] = mp[x][y].d[1] = -1;}if(!rest[x+1][y]){rest[x+1][y] = 1;mp[x+1][y].d[3] = mp[x+1][y].d[0] = mp[x+1][y].d[1] = -1;}}else{++x;mp[x][y].d[0] = 1;mp[x][y+1].d[1] = 1;if(!rest[x][y]){rest[x][y] = 1;mp[x][y].d[1] = mp[x][y].d[2] = mp[x][y].d[3] = -1;}if(!rest[x][y+1]){rest[x][y+1] = 1;mp[x][y+1].d[2] = mp[x][y+1].d[0] = mp[x][y+1].d[3] = -1;}}}}}void SetDoor(){int x,y,d;while(n–){scanf(“%d %d %d”,&x,&y,&d);if(d){mp[x][y+1].d[3] = 0;mp[x+1][y+1].d[2] = 0;}else{mp[x+1][y].d[0] = 0;mp[x+1][y+1].d[1] = 0;}}}int Bfs(int x,int y){int i,xx,yy;mp[x][y].st = 0;queue <pair<int,int> >q;q.push(pair<int,int> (x,y));vis[x][y] = 1;if(!rest[x][y]) return 0;while(!q.empty()){x = q.front().first;y = q.front().second;q.pop();for(i = 0; i < 4; ++i){xx = x + dirx[i];yy = y + diry[i];if(mp[x][y].d[i] == -1) return mp[x][y].st;else if(!mp[x][y].d[i] &&!vis[xx][yy]){vis[xx][yy] = 1;mp[xx][yy].st = mp[x][y].st+1;q.push(pair<int,int> (xx,yy));}}}return -1;}int main(){//freopen(“in.txt”,”r”,stdin);double x,y;while(~scanf(“%d %d”,&m,&n) && m != -1){Init();SetWall();SetDoor();scanf(“%lf %lf”,&x,&y);if(x < 0|| y < 0 || x > 199 || y > 199 ||(n == 0 && m == 0)) printf(“0\n”);else printf(“%d\n”,Bfs((int)(x+1),(int)(y+1)));}return 0;}
，爱情从希望开始，也由绝望结束。死心了，
