Cod sursa(job #2487125)

Utilizator radudavid98David Radu-Andrei radudavid98 Data 3 noiembrie 2019 23:35:04
Problema Car Scor 0
Compilator c-64 Status done
Runda Arhiva de probleme Marime 3.64 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 h1 = last->i - i_exp;
    if(h1<0) h1 = 0 - h1;
    int h2 = last->j - j_exp;
    if(h2<0) h2 = 0 - h2;
    //printf("%d", h1+h2);
    return h1+h2;

;}

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;}
    else return 1;
    /*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;
    };*/
};

void move(int a, int b){
   // printf("\n {%d, %d} -> {%d, %d} - %d",last->i+1, last->j+1, last->i+a+1, last->j+b+1, last->score);
    last->lmove++;
    matrice[last->i][last->j] = 1;

    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 eighth_move(){
    MUTARE *p;
    p = last;
    if (p==first){end = 1; return;}
        else {
            last = p->last;
            matrice[last->i][last->j] = 0;
           // printf("\n {%d, %d} -> {%d, %d}",p->i, p->j, last->i, last->j);
            free(p);
            last -> next = 0;
            movecount--;
        }
};

void start(){
    while(!end){
    if(last->i==fi&&last->j==fj && last-> score < score) score = last->score;
    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 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;
};