Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define rep(a,b) for(int a = 0; a < b; a++)
- #define ln printf("\n")
- using namespace std;
- typedef long long ll;
- typedef pair<int,int> pii;
- int caso = 1;
- int n;
- int sx, sy;
- int dx[4] = {0,0,1,-1};
- int dy[4] = {1,-1,0,0};
- bool get(int y, int x, ll v){
- int pos = y*n+x;
- return (v & (1 << pos)) != 0;
- }
- ll set1(int y, int x, ll v){
- int pos = y*n+x;
- return v | (1 << pos);
- }
- ll set0(int y, int x, ll v){
- int pos = y*n+x;
- return v & (~(1<<pos));
- }
- void print(ll v){
- rep(i,n){
- rep(j,n){
- printf("%d", get(i,j,v));
- }
- ln;
- }
- ln;
- }
- int r[10][10];
- char buf[10];
- bool read() {
- scanf("%d %d %d", &n, &sy, &sx);
- //printf("%d %d
- if(!(n|sy|sx)) return false;
- sx--;
- sy--;
- rep(i,n){
- scanf("%s", buf);
- rep(j,n){
- if(buf[j] == '.') r[i][j] = 0;
- else if(buf[j] == 'E') r[i][j] = 9;
- else r[i][j] = buf[j]-48;
- //printf("%d", r[i][j]);
- }
- //ln;
- }
- //ln;
- return true;
- }
- struct state{
- ll box;
- ll cell;
- char x;
- char y;
- bool operator < (const state & b) const{
- if(box == b.box){
- if(cell == b.cell){
- if(x == b.x){
- return y < b.y;
- }
- return x < b.x;
- }
- return cell < b.cell;
- }
- return box < b.box;
- }
- };
- bool valid(int y, int x){
- return y >= 0 && y < n && x >= 0 && x < n;
- }
- ll top(int y, int x, ll cell, int ty, int tx){
- //printf("Toping %d %d\n", y, x);
- int h = r[y][x];
- //printf("h = %d\n", h);
- cell = set0(y,x,cell);
- //printf("Setei %d %d zero\n", y, x);
- x += tx;
- y += ty;
- rep(i,h){
- //printf("valid %d %d = %d\n", ty, tx, valid(ty,tx));
- if(!valid(y,x)) return 0;
- //printf("get %d %d = %d\n", ty, tx, get(ty,tx,cell));
- if(get(y,x,cell)) return 0;
- cell = set1(y,x,cell);
- //printf("Setei %d %d 0\n", y, x);
- x += tx;
- y += ty;
- }
- return cell;
- }
- void process(){
- state start;
- start.box = 0;
- start.cell = 0;
- start.x = sx;
- start.y = sy;
- rep(i,n){
- rep(j,n){
- if(r[i][j]){
- start.cell = set1(i,j,start.cell);
- if(r[i][j] && r[i][j] != 9){
- start.box = set1(i,j,start.box);
- }
- }
- }
- }
- queue<state> bfs;
- map<state,int> mark;
- mark[start] = 1;
- bfs.push(start);
- int cell;
- state c;
- state temp;
- int dist;
- int ty,tx;
- //print(start.box);
- //print(start.cell);
- //start.cell = top(start.y, start.x, start.cell, 0, 1);
- //print(start.cell);
- //print(start.box);
- //while(1);
- while(!bfs.empty()){
- c = bfs.front();
- bfs.pop();
- dist = mark[c];
- if(r[c.y][c.x] == 9){
- printf("%d\n", mark[c]-1);
- //print(c.cell);
- return;
- }
- if(get(c.y,c.x,c.box)){
- rep(i,4){
- cell = top(c.y,c.x,c.cell,dy[i],dx[i]);
- if(cell){
- temp = c;
- temp.cell = cell;
- temp.box = set0(c.y,c.x,temp.box);
- temp.y += dy[i];
- temp.x += dx[i];
- if(mark[temp] == 0){
- mark[temp] = dist+1;
- bfs.push(temp);
- }
- }
- }
- }
- rep(i,4){
- ty = c.y+dy[i];
- tx = c.x+dx[i];
- if(!valid(ty,tx)) continue;
- if(get(ty,tx,c.cell)){
- temp = c;
- temp.x = tx;
- temp.y = ty;
- if(mark[temp] == 0){
- mark[temp] = dist+1;
- bfs.push(temp);
- }
- }
- }
- }
- printf("Impossible.\n");
- }
- int main() {
- int t = -1;
- //scanf("%d", &t);
- while( t-- && read() ) process();
- return 0;
- }
Add Comment
Please, Sign In to add comment