Cod sursa(job #2487096)

Utilizator radudavid98David Radu-Andrei radudavid98 Data 3 noiembrie 2019 22:17:22
Problema Car Scor 0
Compilator c-32 Status done
Runda Arhiva de probleme Marime 3.61 kb
#include <stdio.h>
#include <stdlib.h>


typedef struct mutare{
    int i; //cordonata i de pe care se porneste mutarea
    int j; //coordonata j de pe care se porneste mutarea
    int lmove;
    struct MUTARE *next;
    struct MUTARE *last;
    int score;
} MUTARE;
int n, m, si, sj, fi,fj, s, movecount, score, end;
int matrice[500][500];
MUTARE *first, *last;
int minmoves;
int score;

void read(){
    FILE *fp;
    fp = fopen("car.in","r");
    fscanf(fp,"%d%d%d%d%d%d", &n,&m,&si, &sj, &fi, &fj);
    int i, j;
    si = si-1; sj = sj-1; fi = fi-1; fj = fj-1;
    int p;
    for(i = 0; i<n; i++)
        for (j = 0; j<m;j++){

            fscanf(fp, "%d", &p);
            matrice[i][j]=p;
    }
    fclose(fp);

};

void write(){
    if(score ==n*m*3) score = -1;
    FILE *fp = fopen("car.out", "w");
    fprintf(fp,"%d", score);
    fclose(fp);
}

int angle(){
    MUTARE *p1, *p2;
    p1 = last->last;
    p2 = p1->last; //ne imaginam 2 vectori in plan;
    int i_exp = p1-> i + (p1->i - p2->i);
    int j_exp = p1 -> j + (p1->j - p2->j);
    int h = (last -> i - i_exp) * (last -> i - i_exp)+ (last->j - j_exp)*(last->j - j_exp);
    switch (h) {
        case 0: return 0;
        case 1: return 1;
        case 2: return 2;
        case 3: return 3;
    };

}

int check_legality(int a, int b){   //a si b reprezinta numarul care trebuie adaugat la i si j pt noua mutare

    int i = last->i+a, j = last->j+b;  // coordonatele casutei verificat
    if(matrice[i][j] == 1 || i < 0 || j < 0|| i>=n|| j >=m)  {return 0;}
    int k;
    MUTARE *p;
    p=first;
    for(k = 0; k<movecount; k++){
        if(p->i == i && p->j ==j) return 0;
        if(p!=last)p = p->next;
    };
    return 1;
}

void move(int a, int b){
   // printf("\n {%d, %d} -> {%d, %d}",last->i, last->j, last->i+a, last->j+b);
    last->lmove++;
    MUTARE *p = malloc(s);
    p->i = last->i+a;
    p->j = last ->j+b;
    p->lmove = 0;
    p->last= last;
    p->next = 0;
    last->next = p;
    last= p;
    movecount++;
    p = last->last;
    if(movecount >1) last->score = p->score+angle(); else last->score = 0;
}

void move_or_dont(int a, int b){
    if(check_legality(a, b)) move(a, b);
        else last->lmove++;
}

void start(){
    while(!end){
    if(last->i==fi&&last->j==fj && last-> score < score) score = last->score;
    MUTARE *p ;
    if(last->score<score)
    switch(last->lmove){
            case 0:move_or_dont(-1,0); break;
            case 1:move_or_dont(-1,1); break;
            case 2:move_or_dont(0,1); break;
            case 3:move_or_dont(1,1); break;
            case 4:move_or_dont(1,0); break;
            case 5:move_or_dont(1,-1); break;
            case 6:move_or_dont(0,-1); break;
            case 7:move_or_dont(-1,-1); break;
            case 8: eighth_move();
                break;
        } else eighth_move();

    }
};
void eighth_move(){
    MUTARE *p;
    p = last;
    if (p==first){end = 1; return;}
        else {
            last = p->last;
           // printf("\n {%d, %d} -> {%d, %d}",p->i, p->j, last->i, last->j);
            free(p);
            last -> next = 0;
            movecount--;
        }
}

void init_list(){
    first = 0;
    last = 0;
    movecount = 0;
    s = sizeof(MUTARE);
    first = malloc(s);
    first -> i = si;
    first -> j = sj;
    first -> next = 0;
    first -> last = 0;
    first -> score = 0;
    first->lmove = 0;
    last = first;
    minmoves = n*m;
    score = 3*n*m;
    end = 0;

};

int main()
{
    read();
    init_list();
    start();
    write();
    return 0;
};