Advertisement
ipilot

G

Oct 28th, 2012
53
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.28 KB | None | 0 0
  1. #pragma warning(disable: 4996)
  2. #pragma comment(linker,"/STACK:64000000")
  3. #include <iostream>
  4. #include <sstream>
  5. #include <stdio.h>
  6. #include <memory.h>
  7. #include <algorithm>
  8. #include <map>
  9. #include <string>
  10. #include <cstring>
  11. #include <vector>
  12. #include <cmath>
  13. #include <queue>
  14. #include <deque>
  15. #include <stack>
  16. #include <cassert>
  17. #include <time.h>
  18. #include <bitset>
  19.  
  20. using namespace std;
  21.  
  22. #define mp make_pair
  23. #define pb push_back
  24. #define _(a,b) memset( (a), b, sizeof( a ) )
  25. #define all(a) a.begin(), a.end()
  26. #define sz(a) (int)a.size()
  27. #define foreach(struct, iterator) for (iterator=struct.begin(); iterator != struct.end(); ++iterator)
  28. #define forn(i, n) for (i=0; i < n; i++)
  29. #define forab(i, a, b) for (i=a; i < b; i++)
  30.  
  31. typedef unsigned long long ull;
  32. typedef long long lint;
  33. typedef pair < int , int > pii;
  34. typedef long double ld;
  35.  
  36. const int INF = 1000 * 1000 * 1000;
  37. const lint LINF = 1000000000000000000LL;
  38. const double eps = 1e-9;
  39.    
  40. void prepare(string s)
  41. {
  42. #ifndef _DEBUG
  43.     freopen("input.txt", "r", stdin);
  44. #else
  45.     if (sz(s) != 0)
  46.     {
  47.         freopen((s + ".in").c_str(),"r",stdin);
  48.         freopen((s + ".out").c_str(),"w",stdout);
  49.     }
  50. #endif
  51. }
  52.  
  53. char lab[10][16];
  54. pii st, d[3]={mp(1, 0), mp(0, 1), mp(0, -1)};
  55. bool used[10][16];
  56. int L[10][16];
  57. vector <int> ans;
  58.  
  59. bool inlab(pii pos)
  60. {
  61.     return (pos.first >= 0) && (pos.first < 10) && (pos.second >= 0) && (pos.second < 16);
  62. }
  63.  
  64. void dfs(pii pos)
  65. {
  66.     int i;
  67.     pii nd;
  68.     used[pos.first][pos.second]=true;
  69.     L[pos.first][pos.second]=1;
  70.     if (pos.first < 9)
  71.     {
  72.         for (i=0; i<3; i++)
  73.         {
  74.             nd=mp(pos.first+d[i].first, pos.second+d[i].second);
  75.             if (inlab(nd) && (!used[nd.first][nd.second]) && (lab[nd.first][nd.second] == '0'))
  76.             {
  77.                 if (i == 0) i=3;
  78.                 dfs(nd);
  79.             }
  80.         }
  81.     }
  82. }
  83.  
  84. int main()
  85. {
  86.     int i, j;
  87.     prepare("lines");
  88.     forn(i, 10)
  89.     {
  90.         forn(j, 16)
  91.         {
  92.             lab[i][j]=getchar();
  93.             if (lab[i][j] == 'x') st=mp(i, j);
  94.             if (lab[i][j] == '1')
  95.             {
  96.                 used[i][j]=true;
  97.                 L[i][j]=-1;
  98.             }
  99.         }
  100.         getchar();
  101.     }
  102.     dfs(st);
  103.     forn(i, 16)
  104.         if (L[9][i] == 1)   ans.pb(i+1);
  105.     if (sz(ans) == 0) cout << "IMPOSSIBLE";
  106.     else
  107.     {
  108.         forn(i, sz(ans)-1) cout << ans[i] << " ";
  109.         cout << ans.back();
  110.     }
  111.     return 0;
  112. }
  113.  
  114. //000000*x********
  115. //111111*11111111*
  116. //****************
  117. //*11111111*111111
  118. //************0000
  119. //1111*111111*1110
  120. //0*****1100******
  121. //1*11111001*11111
  122. //****01001****000
  123. //111*11011*11*110
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement