题目描述
现在有一片树林，小B很想知道，最少需要多少步能围绕树林走一圈，最后回到起点．他能上下左右走，也能走对角线格子。 土地被分成RR行CC列1≤R≤50,1≤C≤501≤R≤50,1≤C≤50，下面是一张样例的地图，其中“.”表示小B可以走的空地，"X"表示树林，"*”表示起点。而小B走的最近的路己经特别地用“+”表示出来。
.......
...X...
..XXX..
...XXX.
...X...
......*题目保证，一定有合法解并且有且只有一片树林，树林一定是上下左右联通的。
输入数据
第11行输入RR和CC，接下来RR行CC列表示一张地图。地图中的符号如题干所述。
输出数据
输出最少的步数。
样例输入
6 7
.......
...X...
..XXX..
...XXX.
...X...
......*样例输出
13数据范围
对于40%40%的数据，R,C≤12R,C≤12 对于60%60%的数据，R,C≤30R,C≤30 对于100%100%的数据，R,C≤50
题目分析
这是一道搜索题，记忆化即可。
最近好久没更新了，我来更新一发。
#include<bits/stdc++.h>
using namespace std;
bitset<>vis[];
int n,m,a[][],dis[][],ans,sx,sy,ex,ey;
const int dx[]={,,,-,,,-,-}, dy[]={,-,,,,-,,-};
queue<pair<int,int> >q;
inline char gc(){
static char buf[],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,,,stdin),p1==p2)?EOF:*p1++;
}signed main(){freopen("grove.in","r",stdin),freopen("grove.out","w",stdout),cin>>n>>m;
if (n==&&m==) {puts("");return ;}
for (int i=;i<=n;++i){gc();
for (int j=; j<=m; ++j){
char c=gc();
if (c!='X') a[i][j]=;
if(c=='*') sx=i,sy=j;
if(c=='X') ex=i,ey=j;
}}q.push(make_pair(sx,sy)),vis[sx][sy]=;
while(q.size()){int x=q.front().first,y=q.front().second;q.pop();
for (int xx,yy,i=;i<;++i){xx=x+dx[i],yy=y+dy[i];
if (xx&&xx<=n&&yy&&yy<=m&&!vis[xx][yy]&&a[xx][yy]){
if(y<=ey&&(x==ex&&xx==ex-||x==ex-&&xx==ex)) continue;
dis[xx][yy]=dis[x][y]+,vis[xx][yy]=,q.push(make_pair(xx,yy));
}}}ans=;
for (int i=;i<=ey;++i)if(a[ex][i]){
if(a[ex-][i]) ans=min(ans,dis[ex][i]+dis[ex-][i]);
if(i+<=m&&a[ex-][i+]) ans=min(ans,dis[ex][i]+dis[ex-][i+]);
if(i>=&&a[ex-][i-]) ans=min(ans,dis[ex][i]+dis[ex-][i-]);
}printf("%d",++ans);
}