贪吃蛇

思路

• 因为求到达终点的最短距离，所以我们用bfs来求
• 注意单位转换

代码

// Problem: 贪吃蛇
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/9986/I
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
#define debug(a) cout<<#a<<":"<<a<<"\n"
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=110;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-6;
const double PI=acos(-1.0);

int n,m;
char c[N][N];
int opx,opy,edx,edy;
bool st[N][N];
int dis[N][N];
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};

int bfs(){
    queue<pii> q;
    q.push({opx,opy});
    st[opx][opy]=1;
    while(!q.empty()){
        auto t=q.front();q.pop();
        if(t.X==edx&&t.Y==edy) return dis[edx][edy];
        for(int i=0;i<4;i++){
            int xx=t.X+dx[i],yy=t.Y+dy[i];
            if(xx<1||yy<1||xx>n||yy>m) continue;
            if(c[xx][yy]=='#') continue;
            if(st[xx][yy]) continue;
            st[xx][yy]=1;
            dis[xx][yy]=dis[t.X][t.Y]+1;
            q.push({xx,yy});
        }
    }
    return -1;
}


void solve(){
    cin>>n>>m;
    cin>>opx>>opy>>edx>>edy;
    rep(i,1,n) rep(j,1,m) cin>>c[i][j];
    int ans=bfs();
    if(ans==-1) cout<<-1<<"\n";
    else cout<<1ll*100*ans<<"\n";
}


int main(){
    ios::sync_with_stdio(0);cin.tie(0);
//    int t;cin>>t;while(t--)
    solve();
    return 0;
}