fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4. pair<int,int>p;
  5. vector<pair<int,int> >v[90002];
  6. int n,m,pi;
  7. int fr,ix,iy;
  8. int a[303][303];
  9. int dis[303][303];
  10. int bfs(int ii,int jj){
  11.     for(int i=0;i<=300;i++)for(int j=0;j<=300;j++)dis[i][j]=100000000;
  12.     queue<pair<int,int> >Q;
  13.     if(a[ii][jj]!=1){
  14.         for(int i=0;i<v[0].size();i++){
  15.             p=v[0][i];
  16.             int x=p.first;
  17.             int y=p.second;
  18.             int ds=abs(ii-x) + abs(y-jj);
  19.             dis[x][y]=ds;
  20.             //cout<<dis[x][y]<<" "<<x<<" "<<y<<endl;
  21.             Q.push(make_pair(x,y));
  22.         }
  23.     }
  24.     else{
  25.          Q.push(make_pair(ii,jj));
  26.          dis[1][1]=0;
  27.     }
  28.     while(!Q.empty()){
  29.         p=Q.front();
  30.         Q.pop();
  31.         int x=p.first,y=p.second;
  32.         //printf("%d %d dis=%d\n",x,y,dis[x][y]);
  33.         int ch=a[x][y];
  34.         for(int i=0;i<v[ch].size();i++){
  35.             p=v[ch][i];
  36.             int xx=p.first,yy=p.second;
  37.             int ds=abs(x-xx)+abs(y-yy);
  38.             //printf("%d %d %d\n",dis[xx][yy],xx,yy);
  39.             if(dis[x][y]+ds < dis[xx][yy]){
  40.                 dis[xx][yy]=dis[x][y]+ds;
  41.  
  42.                 Q.push(make_pair(xx,yy));
  43.             }
  44.         }
  45.     }
  46.     return dis[ix][iy];
  47. }
  48. int main(void)
  49. {
  50.     int n,m,pi;
  51.     scanf("%d%d%d",&n,&m,&pi);
  52.     for(int i=1;i<=n;i++){
  53.         for(int j=1;j<=m;j++){
  54.             int x;
  55.             scanf("%d",&x);
  56.             a[i][j]=x;
  57.             v[x-1].push_back(make_pair(i,j));
  58.             if(x==pi)ix=i,iy=j;
  59.         }
  60.     }
  61.     int ans=bfs(1,1);
  62.     printf("%d\n",ans);
  63.  
  64.     return 0;
  65. }
  66.  
Success #stdin #stdout 0s 5236KB
comments (?)
stdin
copy 
3 4 3
2 1 1 1
1 1 1 1
2 1 1 3
stdout
copy 
5
https://ideone.com/1Tum2W
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!