wa on 2
查看原帖
wa on 2
835944
gyttnnd楼主2023/2/24 21:20
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;

const int inf=191919810;
int n,m;
char map[509][509];
struct node
{
    int next,v;
};
vector<node> a[250009];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
struct edge
{
    int u,d;
    bool operator <(const edge& rhs) const
    {
        return d>rhs.d;
    }
};
int dis[250009];

void d(int x)
{
    for(int i=0;i<=n*m;i++)
    {
        dis[i]=inf;
    }
    dis[x]=0;
    priority_queue<edge> q;
    q.push(edge{x,0});
    while(!q.empty())
    {
        edge p=q.top();
        q.pop();
        int u=p.u;
        int d=p.d;
        for(int i=0;i<a[u].size();i++)
        {
            int v=a[u][i].v;
            int w=a[u][i].next;
            //cout<<w<<"\n";
            if(dis[u]+v<dis[w])
            {
                dis[w]=dis[u]+v;
                q.push(edge{w,dis[w]});
            }
        }
    }
}

int main()
{
    while(cin>>n&&cin>>m)
    {
        a->clear();
        memset(map,'0',sizeof(map));
        int x1,y1,x2,y2;
        if(n==0&&m==0)
        {
            return 0;
        }
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                cin>>map[i][j];
        for(int x=0;x<n;x++)
        {
            for(int y=0;y<m;y++)
            {
                for(int k=0;k<4;k++)
                {
                    int ux=x+dx[k];
                    int uy=y+dy[k];
                    if(ux<0||ux>=n||uy<0||uy>=m)
                    continue;
                    if(map[x][y]==map[ux][uy])
                    {
                        node p;
                        p.next=ux*m+uy;
                        p.v=0;
                        a[x*m+y].push_back(p);
                    }
                    else 
                    {
                        node p;
                        p.next=ux*m+uy;
                        p.v=1;
                        a[x*m+y].push_back(p);
                    }
                }
            }
        }
        cin>>x1>>y1>>x2>>y2;
        if(x2==x1&&y2==y1)
        {
            cout<<"0\n";
            continue;
        }
        d(x1*m+y1);
        cout<<dis[x2*m+y2]<<"\n";
    }
    return 0;
}

2023/2/24 21:20
加载中...