Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- int m,n,i,j,ans=0,a,b;
- bool vis[110][110];
- string s[110];
- int dx[]= {0,1,0,-1};
- int dy[]= {1,0,-1,0};
- bool check(int x,int y)
- {
- return x>=0 && x<m && y>=0 && y<n && vis[x][y]==false && s[x][y]!='#';
- }
- void bfs(int x,int y)
- {
- int j=0;
- queue<pair<int,int> > q;
- q.push(make_pair(x,y));
- vis[x][y]=true;
- while(!q.empty())
- {
- pair<int,int>p;
- p=q.front();
- q.pop();
- for(int i=0; i<4; i++)
- {
- int vx,vy;
- vx=p.first+dx[i];
- vy=p.second+dy[i];
- if(check(vx,vy))
- {
- vis[vx][vy]=true;
- q.push(make_pair(vx,vy));
- if(j%2==0) ans+=a;
- else ans+=b;
- j++;
- }
- }
- }
- }
- int main()
- {
- cin>>n>>m;
- cin>>a>>b;
- for(i=0; i<m; i++)
- {
- cin>>s[i];
- }
- for(i=0; i<m; i++)
- {
- for(j=0; j<n; j++)
- {
- vis[i][j]=false;
- }
- }
- bfs(0,0);
- if(vis[m-1][n-1]== false ) cout<<"IMPOSSIBLE"<<endl;
- else cout<<ans<<endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement