Paste Search Dynamic
Recent pastes
struct tile
  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4. typedef struct tile{
  5.     int y;
  6.     int x;
  7.     int t;
  8.     int chance;
  9. }tile;
  10. int n,m,t=-1;
  11. int dy[] ={-1,0,0,1}, dx[] ={0,-1,1,0};
  12. bool v[1000][1000];
  13. string a[1000];
  14. void bfs(){
  15.     queue<tile> q;
  16.     v[1][1]=true;
  17.     q.push({0,0,1,1});
  18.     while(!q.empty()){
  19.         int cy = q.front().y;
  20.         int cx = q.front().x;
  21.         int ct = q.front().t;
  22.         int chk = q.front().chance;
  23.         q.pop();
  24.         if(cy==n-1&&cx==m-1){
  25.             t=ct;
  26.             return;
  27.         }
  28.         for(int i=0; i<4; i++){
  29.             int ny = cy+dy[i];
  30.             int nx = cx+dx[i];
  31.             int nc = chk;
  32.             if(ny<0||nx<0||ny>=n||nx>=m||v[ny][nx])
  33.                 continue;
  34.             else if(a[ny][nx]=='0'||nc){
  35.             if(a[ny][nx]=='1') nc=0;
  36.             v[ny][nx]=true;  
  37.             q.push({ny,nx,ct+1,nc});
  38. cout<<nc<<'n';}
  39.        
  40.     }}
  41. }
  42. int main(){
  43.     cin.tie(0);
  44.     cin.sync_with_stdio(false);
  45.     cin>>n>>m;
  46.     for(int i=0; i<n; i++)
  47.         cin>>a[i];
  48.     bfs();
  49.     cout<<t;
  50. }
Parsed in 0.005 seconds