http://acm.hdu.edu.cn/showproblem.php?pid=3023

#include<string.h>
#include<stdio.h>
#include<queue>
using namespace std;
int n, m;
int sx, sy, ex, ey;
char graph [1005][1005];
int dis[1005][1005];
int chang[1005][1005];
bool vis[1005][1005];
struct point{
    int x, y, change, step;
    bool operator < (const point& b)const{
        if (change == b.change){ return step > b.step; }
        return change > b.change;
    }
};
int to[8][2]={{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};
void BFS(){
        priority_queue<point> que;
        memset(dis, 0x3f, sizeof(dis));
        dis[sx][sy] = 1;
        memset(chang, 0x3f, sizeof(chang));
        chang[sx][sy] = 0;
        memset(vis, 0, sizeof(vis));
        que.push({ sx, sy, 0, 1 });
        while (!que.empty())
        {
            point curr = que.top();
            que.pop();
            vis[curr.x][curr.y] = 1;
            if (curr.x == ex&&curr.y == ey)break;
            for (int i = 0; i < 8; i++){
                point next = { curr.x + to[i][0], curr.y + to[i][1], curr.change, curr.step + 1 };
                if (next.x >= 0 && next.x < n&&next.y >= 0 && next.y < m&&graph[next.x][next.y]!='0'&&vis[next.x][next.y] == 0){
                    if (graph[next.x][next.y] != graph[curr.x][curr.y]){
                        next.change++;
                }
                if (next.change < chang[next.x][next.y]||(next.change==chang[next.x][next.y]&&next.step<dis[next.x][next.y])){
                        chang[next.x][next.y] = next.change;
                        dis[next.x][next.y] = next.step;
                        que.push(next);
                }
            }
        }
    }
   // while (!que.empty())que.pop();
}

int main(){
    while (~scanf("%d%d", &n, &m)){
        scanf("%d%d%d%d", &sx, &sy, &ex, &ey);
        sx--, sy--, ex--, ey--;
        for(int i=0;i<n;i++)
        {
            getchar();
            for(int j=0;j<m;j++)
            {
                //scanf("%c",&G[i][j]);
                //cin>>G[i][j];
                graph[i][j]=getchar();
            }
                //getchar();
        }
        BFS();
        if (chang[ex][ey] == 0x3f3f3f3f){ printf("0 0\n"); }
        else{ printf("%d %d\n", dis[ex][ey], chang[ex][ey]); }
    }
    return 0;
}