fork 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]=='#')
  32.            {
  33. 			if (temp.dist+1>=arr[nx][ny])
  34.             pq.push(mp(temp.dist+1,nx,ny));
  35.             else
  36.             pq.push(mp(arr[nx][ny],nx,ny));
  37.       	   } else
  38.  
  39.            if(nm[nx][ny]=='.')
  40.             pq.push(mp(temp.dist+1,nx,ny));
  41.        }
  42.    }
  43. }
  44. int main()
  45. {
  46.     ios_base::sync_with_stdio(false);
  47.     cin.tie(NULL);
  48.     int t;cin>>t;
  49.     while(t--)
  50.     {
  51.         cin>>m>>n;
  52.         for(int i=0;i<m;i++)
  53.             cin>>nm[i];
  54.         for(int i=0;i<m;i++)
  55.         {
  56.             for(int j=0;j<n;j++)
  57.             {
  58.                 cin>>arr[i][j];
  59.             }
  60.         }
  61.         int x1,y1;
  62.         cin>>x1>>y1>>x2>>y2;
  63.         memset(visited,false,sizeof visited);
  64.         cout<<dfs(x1,y1)<<"\n";
  65.     }
  66.     return 0;
  67. }
Success #stdin #stdout 0s 3072KB
comments (?)
stdin
copy 
2

1 5

..#..

0 0 1 0 0

0 0

0 4

3 3

.##

##.

##.

0 1 2

3 4 0

6 7 0

0 0

2 2
stdout
copy 
4
4
https://ideone.com/mcT8Kx
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!