Guest User

Untitled

a guest
Jul 14th, 2011
123
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3. #include <math.h>
  4. #include <algorithm>
  5. #include <stack>
  6. #include <vector>
  7. #include <string.h>
  8. #include <string>
  9. #include <queue>
  10. #include <deque>
  11.  
  12. using namespace std;
  13.  
  14. struct point {
  15.     int x,y;
  16. };
  17.  
  18. int main()
  19. {
  20.     freopen("input.txt","r",stdin);
  21.     //freopen("output.txt","w",stdout);
  22.     int n,m,i,j;       
  23.     string s;
  24.     cin>>n>>m;
  25.     int map[n][m];
  26.     int used[n][m];
  27.     memset(used,0,sizeof(used));
  28.     int dx[] = {0,-1,0,1};
  29.     int dy[] = {-1,0,1,0};
  30.     point start, end;
  31.     for (i=0; i<n; ++i) {
  32.         cin>>s;
  33.         for (j=0; j<m; ++j) {
  34.             if (s[j]-48 == 0 || s[j]-48 == 1) map[i][j] = s[j]-48;
  35.             else if (s[j] == '#') {
  36.                 start.x = i;
  37.                 start.y = j;
  38.                 used[i][j] = 1;
  39.             } else if (s[j] == '@') {
  40.                 end.x = i;
  41.                 end.y = j;
  42.                 map[i][j] = 0;
  43.             }
  44.         }
  45.     }
  46.     queue <point> q;
  47.     q.push(start);
  48.     while (!q.empty()) {
  49.         point current = q.front();
  50.         q.pop();
  51.         int x1 = current.x;
  52.         int y1 = current.y;
  53.         for (i=0; i<4; ++i) {
  54.             if (x1+dx[i] >= 0 && x1+dx[i] < n && y1+dy[i] >= 0 && y1+dy[i] < m && !used[x1+dx[i]][y1+dy[i]] && !map[x1+dx[i]][y1+dy[i]] ) {
  55.                 used[x1+dx[i]][y1+dy[i]] = 1;
  56.                 point next;
  57.                 next.x = x1+dx[i];
  58.                 next.y = y1+dy[i];
  59.                 q.push(next);
  60.             }
  61.         }
  62.     }
  63.     if (!used[end.x][end.y]) cout<<"NO"; else cout<<"YES";
  64.     return 0;
  65. }
RAW Paste Data