https://ac.nowcoder.com/acm/contest/322/B
C++版本一
题解:BFS+状态压缩
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=4000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,ans;
int a[54000][4000];
char str[7000];
int sx,sy,tx,ty;
int b[9][2];
struct node{
int x,y;
int cnt;
}f,s,tmp;
bool vis[N][N];
int bfs(){
s.x=sx;
s.y=sy;
s.cnt=0;
queue<node>q;
q.push(s);
b[1][0]=0;
b[1][1]=-1;
b[2][0]=1;
b[2][1]=0;
b[4][0]=0;
b[4][1]=1;
b[8][0]=-1;
b[8][1]=0;
vis[sx][sy]=1;
while(!q.empty()){
f=q.front();
q.pop();
tmp=f;
tmp.cnt++;
if(f.x==tx&&f.y==ty){
return f.cnt;
}
for(int i=1;i<=8;i*=2){int tmd=i&a[1][1];
if((int)(a[f.x][f.y]&i)==i){
tmp.x=f.x+b[i][1];
tmp.y=f.y+b[i][0];
if(0<tmp.x&&tmp.x<=n&&0<tmp.y&&tmp.y<=m&&!vis[tmp.x][tmp.y]){
vis[tmp.x][tmp.y]=1;//cout<<tmp.x<<tmp.y<<tmd<<endl;
q.push(tmp);
}
}
}
}
return -1;
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
scanf("%d%d",&n,&m);
getchar();
for(int i=1;i<=2*n+1;i++){
gets(str);
if(i%2){
for(int j=1;j<=2*m+1;j+=2){
if(str[j]==' '){
a[(i+1)/2][(j+1)/2]+=1;
a[(i+1)/2-1][(j+1)/2]+=4;
}
}
}else{
for(int j=0;j<=2*m+1;j+=2){
if(str[j]==' '){
a[(i+1)/2][j/2]+=2;
a[(i+1)/2][j/2+1]+=8;
}
}
for(int j=1;j<=2*m+1;j+=2){
if(str[j]=='S'){
sx=i/2;
sy=(j+1)/2;
}
if(str[j]=='T'){
tx=i/2;
ty=(j+1)/2;
}
}
}
}
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++){
// cout << a[i][j] ;
// }
// cout<< endl;
// }
ans=bfs();
if(ans==-1)
cout << "TRDD Got lost...TAT" << endl;
else
cout << ans+1 << endl;
//cout << "Hello world!" << endl;
return 0;
}
C++版本二
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
using namespace std;
#define RI register int
const int mx=2*3000+100;
int n,m;
int sx,sy,tx,ty;
char mp[mx][mx];
int vis[mx][mx];
int dif[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
struct Node
{
int x;
int y;
int step;
}zb,st;
queue<Node>q;
int bfs(int a,int b)
{
st.x=a;
st.y=b;
vis[a][b]=1;
st.step=1;
q.push(st);
while (!q.empty())
{
zb=q.front();
q.pop();
//printf("(%d,%d)->",zb.x,zb.y);
if (zb.x==tx&&zb.y==ty) return zb.step;
for (int i=0;i<4;++i)
{
st.x=zb.x+dif[i][0];
st.y=zb.y+dif[i][1];
st.step=zb.step+1;
if (st.x==tx&&st.y==ty) return st.step;
if (st.x<1||st.x>2*n+1||st.y<1||st.y>2*m+1) continue;
if (mp[st.x][st.y]!=' ') continue;
if (i<=1)
{
if (mp[st.x][st.y-1]=='+'&&mp[st.x][st.y+1]=='+')
{
st.x=st.x+dif[i][0];
st.y=st.y+dif[i][1];
}
}
else
{
if (mp[st.x+1][st.y]=='+'&&mp[st.x-1][st.y]=='+')
{
st.x=st.x+dif[i][0];
st.y=st.y+dif[i][1];
}
}
if (vis[st.x][st.y]) continue;
vis[st.x][st.y]=1;
q.push(st);
}
}
return 0;
}
int main()
{
scanf("%d%d",&n,&m);
getchar();
int x=2*n+1,y=2*m+1;
for (int i=1;i<=x;++i)
{
gets(mp[i]+1);
for (int j=1;j<=y;++j)
{
if (mp[i][j]=='S')
{
sx=i;
sy=j;
}
else if (mp[i][j]=='T')
{
tx=i;
ty=j;
}
}
}
int res=bfs(sx,sy);
if (res) printf("%d\n",res);
else printf("TRDD Got lost...TAT\n");
}