题面
一个人要从图中的(C)点走到(F)点。
每一秒他可以往上下左右四个方向走一步，只要目标点不是墙'#'。
另外，他可以通过神奇的枪在墙上开两个传送门，枪可以射中上下左右四个方向第一次遇到的墙；如果他站在有传送门的墙边，他就可以花一秒穿越传送门到另外一个传送门面对的点上。
射击产生传送门所花费的时间不计。
传送门同一时间最多存在两个。一旦他射击产生了第三个传送门，那么第一个传送门将会自动消失。
问从点(C)走到点(F)的最短时间。
思路
考虑直接BFS搜索
除了常规四个方向外，本题还可以使用传送门进行传送
所以可以预处理出某一点(P)向四个方向射击能产生传送门的位置(Q)（即某一方向最近的墙的位置），那么从点(P)通过传送门来到墙边这一点(Q)所需要花费的时间也就是距离点(P)最近的墙的距离(+1)
对于上下左右四个方向最近墙的位置，(O(n^2))预处理即可
而对于某个点最近的墙的距离，以墙为起点先搜索一遍整张图，处理完后再BFS起点到终点计算答案
#include<bits/stdc++.h>
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define perr(i,a,b) for(int i=(a);i>(b);i--)
#define all(a) (a).begin(),(a).end()
#define SUM(a) accumulate(all(a),0LL)
#define MIN(a) (*min_element(all(a)))
#define MAX(a) (*max_element(all(a)))
#define mst(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-12;
const double PI=acos(-1.0);
const ll mod=998244353;
const int dx[8]={0,1,0,-1,1,1,-1,-1},dy[8]={1,0,-1,0,1,-1,1,-1};
void debug(){cerr<<'
';}template<typename T,typename... Args>void debug(T x,Args... args){cerr<<"[ "<<x<< " ] , ";debug(args...);}
mt19937 mt19937random(std::chrono::system_clock::now().time_since_epoch().count());
ll getRandom(ll l,ll r){return uniform_int_distribution<ll>(l,r)(mt19937random);}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;}
ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;}
ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;}
int n,m;
char mp[505][505];
int sx,sy,tx,ty;
int lef[505][505],rig[505][505],top[505][505],btm[505][505];
int dis[505][505],rdis[505][505];
inline bool prim(int x,int y)
{
return x>0&&y>0&&x<=n&&y<=m;
}
void solve()
{
rep(i,1,n)
cin>>(mp[i]+1);
queue<pii> q;
mst(dis,INF);
mst(rdis,INF); //某点最近的墙的距离
rep(i,1,n)
rep(j,1,m)
{
if(mp[i][j]=='C')
sx=i,sy=j;
else if(mp[i][j]=='F')
tx=i,ty=j;
else if(mp[i][j]=='#')
{
repp(k,0,4)
{
int x=dx[k]+i,y=dy[k]+j;
if(rdis[x][y]==0)
continue;
if(prim(x,y)&&mp[x][y]!='#')
q.push(pii(x,y)),rdis[x][y]=0;
}
}
}
while(!q.empty()) //先预处理rdis
{
int x=q.front().fi,y=q.front().se;
q.pop();
repp(i,0,4)
{
int px=x+dx[i],py=y+dy[i];
if(prim(px,py)&&mp[px][py]!='#')
{
if(rdis[px][py]>rdis[x][y]+1)
{
rdis[px][py]=rdis[x][y]+1;
q.push(pii(px,py));
}
}
}
}
rep(i,1,n) //处理四个方向上传送门能够到达的点
{
int t=0;
rep(j,1,m)
{
if(mp[i][j]=='#')
{
t=j;
continue;
}
lef[i][j]=t+1;
}
t=n+1;
per(j,m,1)
{
if(mp[i][j]=='#')
{
t=j;
continue;
}
rig[i][j]=t-1;
}
}
rep(j,1,m)
{
int t=0;
rep(i,1,n)
{
if(mp[i][j]=='#')
{
t=i;
continue;
}
top[i][j]=t+1;
}
t=n+1;
per(i,n,1)
{
if(mp[i][j]=='#')
{
t=i;
continue;
}
btm[i][j]=t-1;
}
}
q.push(pii(sx,sy));
dis[sx][sy]=0;
while(!q.empty())
{
int x=q.front().fi,y=q.front().se;
q.pop();
repp(i,0,4) //普通的四个方向
{
int px=x+dx[i],py=y+dy[i];
if(prim(px,py)&&mp[px][py]!='#')
{
if(dis[px][py]>dis[x][y]+1)
{
dis[px][py]=dis[x][y]+1;
q.push(pii(px,py));
}
}
}
int px,py;
px=x,py=lef[x][y]; //向左射击产生传送门能到达的点
if(prim(px,py)&&mp[px][py]!='#')
{
if(dis[px][py]>dis[x][y]+rdis[x][y]+1)
{
dis[px][py]=dis[x][y]+rdis[x][y]+1;
q.push(pii(px,py));
}
}
px=x,py=rig[x][y];
if(prim(px,py)&&mp[px][py]!='#')
{
if(dis[px][py]>dis[x][y]+rdis[x][y]+1)
{
dis[px][py]=dis[x][y]+rdis[x][y]+1;
q.push(pii(px,py));
}
}
px=top[x][y],py=y;
if(prim(px,py)&&mp[px][py]!='#')
{
if(dis[px][py]>dis[x][y]+rdis[x][y]+1)
{
dis[px][py]=dis[x][y]+rdis[x][y]+1;
q.push(pii(px,py));
}
}
px=btm[x][y],py=y;
if(prim(px,py)&&mp[px][py]!='#')
{
if(dis[px][py]>dis[x][y]+rdis[x][y]+1)
{
dis[px][py]=dis[x][y]+rdis[x][y]+1;
q.push(pii(px,py));
}
}
}
if(dis[tx][ty]==INF)
cout<<"nemoguce
";
else
cout<<dis[tx][ty]<<'
';
}
int main()
{
closeSync;
while(cin>>n>>m)
{
solve();
}
return 0;
}