Guest User

Untitled

a guest
Dec 13th, 2018
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.32 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define rep(a,b) for(int a = 0; a < b; a++)
  3. #define ln printf("\n")
  4. using namespace std;
  5. typedef long long ll;
  6. typedef pair<int,int> pii;
  7. int caso = 1;
  8.  
  9. int n;
  10. int sx, sy;
  11. int dx[4] = {0,0,1,-1};
  12. int dy[4] = {1,-1,0,0};
  13.  
  14. bool get(int y, int x, ll v){
  15. int pos = y*n+x;
  16. return (v & (1 << pos)) != 0;
  17. }
  18.  
  19. ll set1(int y, int x, ll v){
  20. int pos = y*n+x;
  21. return v | (1 << pos);
  22. }
  23.  
  24. ll set0(int y, int x, ll v){
  25. int pos = y*n+x;
  26. return v & (~(1<<pos));
  27. }
  28.  
  29. void print(ll v){
  30. rep(i,n){
  31. rep(j,n){
  32. printf("%d", get(i,j,v));
  33. }
  34. ln;
  35. }
  36. ln;
  37. }
  38.  
  39. int r[10][10];
  40. char buf[10];
  41.  
  42. bool read() {
  43. scanf("%d %d %d", &n, &sy, &sx);
  44. //printf("%d %d
  45. if(!(n|sy|sx)) return false;
  46. sx--;
  47. sy--;
  48.  
  49.  
  50. rep(i,n){
  51. scanf("%s", buf);
  52. rep(j,n){
  53. if(buf[j] == '.') r[i][j] = 0;
  54. else if(buf[j] == 'E') r[i][j] = 9;
  55. else r[i][j] = buf[j]-48;
  56. //printf("%d", r[i][j]);
  57. }
  58. //ln;
  59. }
  60. //ln;
  61.  
  62. return true;
  63. }
  64.  
  65. struct state{
  66. ll box;
  67. ll cell;
  68. char x;
  69. char y;
  70.  
  71. bool operator < (const state & b) const{
  72. if(box == b.box){
  73. if(cell == b.cell){
  74. if(x == b.x){
  75. return y < b.y;
  76. }
  77. return x < b.x;
  78. }
  79. return cell < b.cell;
  80. }
  81. return box < b.box;
  82. }
  83. };
  84.  
  85. bool valid(int y, int x){
  86. return y >= 0 && y < n && x >= 0 && x < n;
  87. }
  88.  
  89.  
  90.  
  91. ll top(int y, int x, ll cell, int ty, int tx){
  92. //printf("Toping %d %d\n", y, x);
  93. int h = r[y][x];
  94. //printf("h = %d\n", h);
  95. cell = set0(y,x,cell);
  96. //printf("Setei %d %d zero\n", y, x);
  97. x += tx;
  98. y += ty;
  99.  
  100. rep(i,h){
  101. //printf("valid %d %d = %d\n", ty, tx, valid(ty,tx));
  102. if(!valid(y,x)) return 0;
  103. //printf("get %d %d = %d\n", ty, tx, get(ty,tx,cell));
  104. if(get(y,x,cell)) return 0;
  105. cell = set1(y,x,cell);
  106. //printf("Setei %d %d 0\n", y, x);
  107. x += tx;
  108. y += ty;
  109. }
  110.  
  111. return cell;
  112. }
  113.  
  114. void process(){
  115. state start;
  116. start.box = 0;
  117. start.cell = 0;
  118. start.x = sx;
  119. start.y = sy;
  120.  
  121. rep(i,n){
  122. rep(j,n){
  123. if(r[i][j]){
  124. start.cell = set1(i,j,start.cell);
  125. if(r[i][j] && r[i][j] != 9){
  126. start.box = set1(i,j,start.box);
  127. }
  128. }
  129. }
  130. }
  131.  
  132. queue<state> bfs;
  133. map<state,int> mark;
  134. mark[start] = 1;
  135. bfs.push(start);
  136. int cell;
  137. state c;
  138. state temp;
  139. int dist;
  140. int ty,tx;
  141.  
  142. //print(start.box);
  143. //print(start.cell);
  144. //start.cell = top(start.y, start.x, start.cell, 0, 1);
  145. //print(start.cell);
  146.  
  147. //print(start.box);
  148.  
  149.  
  150.  
  151. //while(1);
  152.  
  153. while(!bfs.empty()){
  154. c = bfs.front();
  155. bfs.pop();
  156. dist = mark[c];
  157.  
  158. if(r[c.y][c.x] == 9){
  159. printf("%d\n", mark[c]-1);
  160. //print(c.cell);
  161. return;
  162. }
  163.  
  164. if(get(c.y,c.x,c.box)){
  165. rep(i,4){
  166. cell = top(c.y,c.x,c.cell,dy[i],dx[i]);
  167. if(cell){
  168. temp = c;
  169. temp.cell = cell;
  170. temp.box = set0(c.y,c.x,temp.box);
  171. temp.y += dy[i];
  172. temp.x += dx[i];
  173. if(mark[temp] == 0){
  174. mark[temp] = dist+1;
  175. bfs.push(temp);
  176. }
  177. }
  178. }
  179. }
  180.  
  181. rep(i,4){
  182. ty = c.y+dy[i];
  183. tx = c.x+dx[i];
  184. if(!valid(ty,tx)) continue;
  185. if(get(ty,tx,c.cell)){
  186. temp = c;
  187. temp.x = tx;
  188. temp.y = ty;
  189. if(mark[temp] == 0){
  190. mark[temp] = dist+1;
  191. bfs.push(temp);
  192. }
  193. }
  194. }
  195. }
  196.  
  197. printf("Impossible.\n");
  198. }
  199.  
  200. int main() {
  201. int t = -1;
  202. //scanf("%d", &t);
  203. while( t-- && read() ) process();
  204. return 0;
  205. }
Add Comment
Please, Sign In to add comment