fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. string nm[205];int arr[205][205];
  4. bool visited[205][205];int m,n;int x2,y2;
  5. int dx[]={1,-1,0,0};
  6. int dy[]={0,0,1,-1};
  7. #define set1 pair< int,pair<int,int> >
  8. #define dist first
  9. #define a second.first
  10. #define b second.second
  11. #define mp(a1,b1,c1) make_pair(a1,make_pair(b1,c1))
  12. int dfs(int x,int y)
  13. {
  14.    priority_queue< set1,vector<set1>,greater<set1> >pq;
  15.    pq.push(mp(0,x,y));
  16.    while(!pq.empty())
  17.    {
  18.        set1 temp=pq.top();pq.pop();
  19.        if(temp.a==x2 && temp.b==y2)
  20.         return temp.dist;
  21.        if(visited[temp.a][temp.b]==true)
  22.         continue;
  23.        //cout<<temp.a<<" "<<temp.b<<temp.dist<<"\n";
  24.        visited[temp.a][temp.b]=true;
  25.        for(int i=0;i<4;i++)
  26.        {
  27.            int nx=temp.a+dx[i];
  28.            int ny=temp.b+dy[i];
  29.            if(nx<0 || nx>=m || ny<0 || ny>=n || visited[nx][ny])
  30.             continue;
  31.            if(nm[nx][ny]=='#' && temp.dist+1>=arr[nx][ny])
  32.             pq.push(mp(temp.dist+1,nx,ny));
  33.            if(nm[nx][ny]=='.')
  34.             pq.push(mp(temp.dist+1,nx,ny));
  35.        }
  36.    }
  37. }
  38. int main()
  39. {
  40.     ios_base::sync_with_stdio(false);
  41.     cin.tie(NULL);
  42.     int t;cin>>t;
  43.     while(t--)
  44.     {
  45.         cin>>m>>n;
  46.         for(int i=0;i<m;i++)
  47.             cin>>nm[i];
  48.         for(int i=0;i<m;i++)
  49.         {
  50.             for(int j=0;j<n;j++)
  51.             {
  52.                 cin>>arr[i][j];
  53.             }
  54.         }
  55.         int x1,y1;
  56.         cin>>x1>>y1>>x2>>y2;
  57.         memset(visited,false,sizeof visited);
  58.         cout<<dfs(x1,y1)<<"\n";
  59.     }
  60.     return 0;
  61. }
Success #stdin #stdout 0s 3072KB
comments (?)
stdin
copy 
1
1 5
..#..
0 0 100 0 0
0 0
0 4
stdout
copy 
0
https://ideone.com/yOiFFG
language:
C++ 4.3.2 (gcc-4.3.2)
created:
9 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!