Cod sursa(job #1173504)

Utilizator CristinaElenaFMI Ciort Elena Cristina CristinaElena Data 19 aprilie 2014 20:47:59
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.09 kb
#include <stdio.h>  
#include <string.h>     
     
long c[2000010];     
long u[2000010];     
long n, m;     
long a[510][510];     
char viz[8][510][510]; 
long dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};     
long dy[] = {0, 1, 1, 1, 0, -1, -1, -1};     

/*
    while (1) {     
        while (pc <= qc) {     
            x = c[pc] & 511;     
            y = (c[pc] >> 9) & 511;    
            if (x == xf && y == yf) {     
                e = 1;     
                break;     
            }     
            dir = c[pc] >> 18;     
			//modific pe cine vizitez
            if (!viz[dir][x + dx[dir]][y + dy[dir]] && !a[x + dx[dir]][y + dy[dir]]) {     
                c[++qc] = x + dx[dir] + ((y + dy[dir]) << 9) + (dir << 18);     
                viz[dir][x + dx[dir]][y + dy[dir]] = 1;     
            }    
            ++pc;     
        }     
        for (i = 0; i <= qc; i++) {     
            x = c[i] & 511;     
            y = (c[i] >> 9) & 511;     
            dir = c[i] >> 18;     
            if (!viz[(dir + 1) & 7][x][y]) {     
                u[++qu] = x + (y << 9) + (((dir + 1) & 7) << 18);     
                viz[(dir + 1) & 7][x][y] = 1;     
            }     
			--dir;    
			//updatez
            if (dir < 0) dir = 7;     
            if (!viz[dir][x][y]) {     
                u[++qu] = x + (y << 9) + (dir << 18);     
                viz[dir][x][y] = 1;     
            }                
        }     
        if (e > 0) {
			break;     
		}
        if (qu == -1) {     
            cost = -1;     
            break;     
        }     
        ++cost;   
		//golesk matricea
        memcpy(c, u, sizeof(c));    
        pc = 0;     
        qc = qu;     
        qu = -1;     
    }     		
*/
     
int main() {     
	long cost = 0, e = 0, i, j, pc = 0, qc = 7, qu = -1, x, y, xb, yb, xf, yf, dir;  	
    freopen("car.in", "r", stdin);     
    freopen("car.out", "w", stdout);     
    scanf("%ld %ld", &n, &m);     
    scanf("%ld %ld %ld %ld", &xb, &yb, &xf, &yf);     
    for (i = 1; i <= n; i++) {    
        for (j = 1; j <= m; j++) {     
            scanf("%ld", &a[i][j]); 
		}			
	}
	//init
    for (i = 0; i <= n + 1; ++i) {     
        a[i][0] = 1;     
        a[i][m + 1] = 1;     
    }     
	//init lap
    for (j = 0; j <= m + 1; ++j) {     
        a[0][j] = 1;     
        a[n + 1][j] = 1;     
    }     
	//dirs
    for (i = 0; i < 8; ++i) {     
        c[i] = xb + (yb << 9) + (i << 18);     
        viz[i][xb][yb] = 1;     
    }     
    while (1) {     
        while (pc <= qc) {     
            x = c[pc] & 511;     
            y = (c[pc] >> 9) & 511;    
            if (x == xf && y == yf) {     
                e = 1;     
                break;     
            }     
            dir = c[pc] >> 18;     
			//modific pe cine vizitez
            if (!viz[dir][x + dx[dir]][y + dy[dir]] && !a[x + dx[dir]][y + dy[dir]]) {     
                c[++qc] = x + dx[dir] + ((y + dy[dir]) << 9) + (dir << 18);     
                viz[dir][x + dx[dir]][y + dy[dir]] = 1;     
            }    
            ++pc;     
        }     
        for (i = 0; i <= qc; i++) {     
            x = c[i] & 511;     
            y = (c[i] >> 9) & 511;     
            dir = c[i] >> 18;     
            if (!viz[(dir + 1) & 7][x][y]) {     
                u[++qu] = x + (y << 9) + (((dir + 1) & 7) << 18);     
                viz[(dir + 1) & 7][x][y] = 1;     
            }     
			--dir;    
			//updatez
            if (dir < 0) dir = 7;     
            if (!viz[dir][x][y]) {     
                u[++qu] = x + (y << 9) + (dir << 18);     
                viz[dir][x][y] = 1;     
            }                
        }     
        if (e > 0) {
			break;     
		}
        if (qu == -1) {     
            cost = -1;     
            break;     
        }     
        ++cost;   
		//golesk matricea
        memcpy(c, u, sizeof(c));    
        pc = 0;     
        qc = qu;     
        qu = -1;     
    }     		
	//afla();
    printf("%ld\n", cost);     
	return 0;     
}