[USACO11OPEN]玉米田迷宫Corn Maze题解

题解"/>

[USACO11OPEN]玉米田迷宫Corn Maze题解

题目链接

洛谷p1825
bzoj3299

以下描述针对于洛谷环境

这一题本来是普通的bfs，但坑点却很多，其中有一个疑似数据问题。

坑点1： 传送门可以多次走

bfs不扩张重复点，这是它比dfs快的原因之一。但这一题传送门可以多次走，比如这个样例：

5 5
#####
#.#.#
#A#A=
#.#@#
#####

传送门是强制传送的，没有选择，所以需要两次经过传送门，传过去再传回来。

解决方案：

就拿样例来说，从@到第四列的A会直接传到第二列的A，可以看做没经过第四列的A，而是直接到了第二列的A，稍微处理一下即可。

处理代码

//如果是传送门就直接跳到另一头
if(mp[xx][yy]>='A'&&mp[xx][yy]<='Z')
{int t=mp[xx][yy]-'A';//x0,y0,x1,y1分别为传送门两端的横纵坐标	xx=xx==x0[t]?x1[t]:x0[t];//跳转yy=yy==y0[t]?y1[t]:y0[t];
}

坑点2： 传送门不配全

疑似数据问题。就第四个点的传送门Z，其他都没问题。虽然洛谷没说，但其它oj都保证了传送门成对出现。

对于我的代码，它会跳转到第0行，第0列，而我判断能走的依据只有不为#，所以就越界了。我就直接把mp[0][0]赋为#，把单独的传送门看成#就行。

code：

#include<iostream>
using namespace std;
const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
char mp[310][310];
int f[310][310],qx[90010],qy[90010],x0[26],y0[26],x1[26],y1[26],q1=1,q2;
int main()
{mp[0][0]='#';//把mp[0][0]赋为#，防止越界int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){cin>>mp[i][j];if(mp[i][j]=='@')//起点入队{qx[++q2]=i;qy[q2]=j;f[i][j]=1;}//预处理传送门两端的横纵坐标if(mp[i][j]>='A'&&mp[i][j]<='Z'){int t=mp[i][j]-'A';if(!x0[t])x0[t]=i,y0[t]=j;else x1[t]=i,y1[t]=j;}}while(q1<=q2){int x=qx[q1],y=qy[q1];for(int i=0;i<4;i++){int xx=x+dx[i],yy=y+dy[i];//如果是传送门就直接跳到另一头if(mp[xx][yy]>='A'&&mp[xx][yy]<='Z'){int t=mp[xx][yy]-'A';xx=xx==x0[t]?x1[t]:x0[t];yy=yy==y0[t]?y1[t]:y0[t];}//照常处理//用f同时代表步数和走没走过if(mp[xx][yy]!='#'&&!f[xx][yy]){f[xx][yy]=f[x][y]+1;qx[++q2]=xx;qy[q2]=yy;if(mp[xx][yy]=='='){//起点步数即为一，所以要减一printf("%d\n",f[xx][yy]-1);return 0;}}}q1++;}return 0;
}