I have problems understanding the asymptotic analysis or complexity, I tried the following link and read the full article, this, however, did not give a final answer to my question, namely:
Should I write complexity for each line of code and summarize them or something else? My teacher did not quite explain how to do this, but he wants it to be done.
Condition: the knight (chess) must cross the matrix of the ice lake (mx n ) and get his friend from the other side of the lake with the given obstacles. Each time he jumps, the cell of the matrix that he jumps becomes an obstacle (ice falls). After he receives his buddy, he must return to the start after another route. The starting point is the bottom corner left cell, his buddy is in the top right cell of the cell
I used Backtracking for this algorithm, and the remaining problem calculates time or asymptotic complexity . Code below:
#include<stdio.h>
#include<conio.h>
#define N 50
typedef struct{
int x;
int y;
} coordonate;
int sol=0,m,n;
coordonate vectSol[N];
void jump(int xL,int yL,int xD,int yD,int obstacole[N][N],int steps,coordonate road[N]);
int main(){
int i,j,x,y,obstacole[N][N],nrObs;
int KnightMatrixRoad[N][N], KnightMatrixBack[N][N];
coordonate pathKnight[N],pathBack[N];
printf("m=");
scanf("%d",&m);
printf("n=");
scanf("%d",&n);
printf("Nr. of obstacles: ");
scanf("%d",&nrObs);
for(i=0;i<nrObs;i++){
printf("Insert obstacle %d through space bar (x,y):",i+1);
scanf("%d %d",&x,&y);
obstacole[y-1][x-1]=1;
}
jump(0,0,m-1,n-1,obstacole,0,pathKnight);
for(i=0;i<=sol;i++){
obstacole[vectSol[i].y][vectSol[i].x]=1;
pathKnight[i]=vectSol[i];
vectSol[i].x=0;
vectSol[i].y=0;
}
sol=obstacole[n-1][m-1]=obstacole[0][0]=0;
jump(m-1,n-1,0,0,obstacole,0,pathBack);
for(i=0;i<=sol;i++){
pathBack[i]=vectSol[i];
vectSol[i].x=0;
vectSol[i].y=0;
}
for(i=0;(pathKnight[i-1].x!=m-1) || (pathKnight[i-1].y!=n-1);i++){
KnightMatrixRoad[pathKnight[i].y][pathKnight[i].x]=i;
}
puts("\nPath to his buddy:\n");
for(i=n-1,sol=0;i>=0;i--){
for(j=0;j<m;j++)
printf("%3d",KnightMatrixRoad[i][j]);
printf("\n\n");
}
for(i=0;((pathBack[i-1].x!=0) || (pathBack[i-1].y!=0)) || i==0;i++){
KnightMatrixBack[pathBack[i].y][pathBack[i].x]=i;
}
puts("\nPath back to starting point:\n");
for(i=n-1,sol=0;i>=0;i--){
for(j=0;j<m;j++)
printf("%3d",KnightMatrixBack[i][j]);
printf("\n\n");
}
getch();
}
void jump(int xLocal,int yLocal,int xDest,int yDest,int obstacole[N][N],int steps,coordonate road[N]){
int i,j;
int tempObstacole[N][N];
for(i=0;i<n;i++)
for(j=0;j<m;j++){
tempObstacole[i][j]=obstacole[i][j];
}
road[steps].x=xLocal;
road[steps].y=yLocal;
if(xLocal==xDest && yLocal==yDest){
if(sol==0 || steps<sol){
for(i=0;i<=sol;i++){
vectSol[i].x=0;
vectSol[i].y=0;
}
sol=steps;
for(i=0;i<=sol;i++)
vectSol[i]=road[i];
}
}
if(sol==0 || steps+1<sol){
tempObstacole[yLocal][xLocal]=1;
if(yLocal+2<n && xLocal+1<m && !(tempObstacole[yLocal+2][xLocal+1]))
jump(xLocal+1,yLocal+2,xDest,yDest,tempObstacole,steps+1,road);
if(yLocal+2<n && xLocal-1>=0 && !(tempObstacole[yLocal+2][xLocal-1]))
jump(xLocal-1,yLocal+2,xDest,yDest,tempObstacole,steps+1,road);
if(yLocal-2>=0 && xLocal+1<m && !(tempObstacole[yLocal-2][xLocal+1]))
jump(xLocal+1,yLocal-2,xDest,yDest,tempObstacole,steps+1,road);
if(yLocal-2>=0 && xLocal-1>=0 && !(tempObstacole[yLocal-2][xLocal-1]))
jump(xLocal-1,yLocal-2,xDest,yDest,tempObstacole,steps+1,road);
if(yLocal+1<n && xLocal+2<m && !(tempObstacole[yLocal+1][xLocal+2]))
jump(xLocal+2,yLocal+1,xDest,yDest,tempObstacole,steps+1,road);
if(yLocal+1<n && xLocal-2>=0 && !(tempObstacole[yLocal+1][xLocal-2]))
jump(xLocal-2,yLocal+1,xDest,yDest,tempObstacole,steps+1,road);
if(yLocal-1>=0 && xLocal+2<m && !(tempObstacole[yLocal-1][xLocal+2]))
jump(xLocal+2,yLocal-1,xDest,yDest,tempObstacole,steps+1,road);
if(yLocal-1>=0 && xLocal-2>=0 && !(tempObstacole[yLocal-1][xLocal-2]))
jump(xLocal-2,yLocal-1,xDest,yDest,tempObstacole,steps+1,road);
}
}