Pagini recente » Cod sursa (job #1724543) | Cod sursa (job #137050) | Cod sursa (job #2419552) | Cod sursa (job #703600) | Cod sursa (job #2487147)
#include <fstream>
#include <iostream>
using namespace std;
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 matricea_scorurilor[500][500];
int n, m, si, sj, fi,fj, movecount, eend;
bool matrice[500][500];
MUTARE *first, *last;
int minmoves;
int score;
void read(){
ifstream fin;
fin.open("car.in");
fin>> n >> m >> si >> sj >> fi >> fj;
int i, j;
si = si-1; sj = sj-1; fi = fi-1; fj = fj-1;
for(i = 0; i<n; i++){
for (j = 0; j<m;j++){
fin>>matrice[i][j];
}
}
fin.close();
};
void write(){
if(score ==n*m*3) score = -1;
ofstream fout;
fout.open("car.out");
fout<< score;
fout.close();
};
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;
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;
};
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 = new MUTARE;
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;
matricea_scorurilor[last->i][last->j] = last->score;
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){eend = 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);
delete(p);
last -> next = 0;
movecount--;
}
};
void start(){
while(!eend){
if(last->i==fi&&last->j==fj && last-> score < score) score = last->score;
if(last->score<score && last->score < matricea_scorurilor[last->i][last->j])
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;
first = new MUTARE;
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;
eend = 0;
};
int main(){
read();
init_list();
start();
write();
return 0;
};