# 找路
:::info
因為對struct不熟，所以就用array來模擬queue
結果WA，只過兩個測資

11/05 20:42 Update:
經過助教指點我重新寫了一下fp_x和fp_y的實作方式
並把判斷depth++的地方移到bfs的最前面判斷
成功過前面四個測資了
但最後一個還是WA
:::
### 思路
## submit 結果
### 新submit結果

舊:
# 新code
## pure

#include<stdio.h>
#include<stdbool.h>
int q_start = 0, q_end = 0/*the index of last value +1*/;
int row, col;
int fp_x = -1;
int fp_y = -1;

void q_push(int val, int q[]){
  if(q_start <= q_end){
    q[q_end] = val;
  }
  else{
    printf("buffer saturated during push\n");
  }
}

int q_pop(int q[]){
  if(q_start <= q_end){
    return q[q_start];
  }
  else{
    printf("buffer saturated during pop %d\n",q_start);
    return -1;
  }
}

int bfs(int map[][col], int x, int y, int depth, int q_x[], int q_y[], bool visited[][col],bool dep_chg){
  if(dep_chg)
     depth++;
  if(map[y][x] == -3){//end condition
    printf("%d\n",depth-1);//depth includes the first block
    return -1;//pop out this function
  }
  else{
    //put the next level value into queue then pop
    //push if pathable and in range and not visited
    if(dep_chg){//if enter next level
      fp_x = -1;//first push x
      fp_y = -1;
    }
    if(x-1 >= 0 && y >= 0 && x-1 < col && y < row && map[y][x-1] != -1 && !visited[y][x-1]){
      //push into queue
      q_push(x-1, q_x);
      q_push(y, q_y);
      q_end++;
      visited[y][x-1] = true;
	  if(fp_x == -1){
		fp_x = x-1;
		fp_y = y;
	  }
    }
    if(x+1 >= 0 && y >= 0 && x+1 < col && y < row && map[y][x+1] != -1 && !visited[y][x+1]){
      //push into queue
      q_push(x+1, q_x);
      q_push(y, q_y);
      q_end++;
      visited[y][x+1] = true;
      if(fp_x == -1){
        fp_x = x + 1;
        fp_y = y;
      }
    }
    if(x >= 0 && y-1 >= 0 && x < col && y-1 < row && map[y-1][x] != -1 && !visited[y-1][x]){
      //push into queue
      q_push(x, q_x);
      q_push(y-1, q_y);
      q_end++;
      visited[y-1][x] = true;
        if(fp_x == -1){
          fp_x = x;
          fp_y = y - 1;
        }
    }
    if(x >= 0 && y+1 >= 0 && x < col && y+1 < row && map[y+1][x] != -1 && !visited[y+1][x]){
      //push into queue
      q_push(x, q_x);
      q_push(y+1, q_y);
      q_end++;
      visited[y+1][x] = true;
      if(fp_x == -1){
        fp_x = x;
        fp_y = y + 1;
      }
    }
    int next_x = q_pop(q_x);
    int next_y = q_pop(q_y);
    q_start++;

    bool whether_next;
    if(next_x != fp_x || next_y != fp_y)
      whether_next = false;
    else
      whether_next = true;
    if(next_x != -1 && next_y != -1){
      if(!whether_next)
        return bfs(map, next_x, next_y, depth, q_x, q_y, visited, false);
      else
        return bfs(map, next_x, next_y, depth, q_x, q_y, visited, true);
    }
    //printf("leave bfs\n");
  }
}

int main(int argc, char *argv[]){
  scanf("%d %d",&row, &col);
  //0: pathable
  //-1: handicap
  //-2: start
  //-3: end
  int x_start, y_start;//the start point
  int map[row][col];
  for(int i = 0; i < row; i++){
    for(int j = 0; j < col; j++){
      scanf("%d", &map[i][j]);
      if(map[i][j] == -2){
        x_start = j;
        y_start = i;
      }
    }
  }
  bool visited[row][col];
  for(int i = 0; i < row; i++){
    for(int  j = 0; j < col; j++){
        visited[i][j] = false;
    }
  }
  int depth = 0;
  int max_size = 1;//max_size of queue
  for(int i = (row + col); i >= (col+1); i--){
    max_size *= i;
  }
  for(int i = 1; i <= row; i++){
    max_size /= i;
  }
  //now max_size is C(row+col,row):max way
  max_size *= (row+col);//max_step:walk close to range
  int q_x[max_size];
  int q_y[max_size];
  for(int i = 0; i < max_size ; i++){
    q_x[i] = -1;
    q_y[i] = -1;
  }
  visited[y_start][x_start] = true;
  bfs(map, x_start, y_start, depth, q_x, q_y, visited, true);
  return 0;
}

## debug版

#include<stdio.h>
#include<stdbool.h>
int q_start = 0, q_end = 0/*the index of last value +1*/;
int row, col;
int fp_x = -1;
int fp_y = -1;
//debug
void print_q(int q_x[],int q_y[]){
  printf("start print q\n");
  for(int i = q_start; i < q_end; i++){
    printf("%d ",q_x[i]);
  }
  printf("\n");
  for(int i = q_start; i < q_end; i++){
    printf("%d ",q_y[i]);
  }
  printf("\n");
}
//debug
void q_push(int val, int q[]){
  if(q_start <= q_end){
    q[q_end] = val;
  }
  else{
    printf("buffer saturated during push\n");
  }
}

int q_pop(int q[]){
  if(q_start <= q_end){
    return q[q_start];
  }
  else{
    printf("buffer saturated during pop %d\n",q_start);
    return -1;
  }
}

int bfs(int map[][col], int x, int y, int depth, int q_x[], int q_y[], bool visited[][col],bool dep_chg){

  //debug
  if(dep_chg)
    printf("call bfs(x:%d,y:%d,dep:%d,dep_chg: true)\n", x, y, depth);
  else
    printf("call bfs(x:%d,y:%d,dep:%d,dep_chg: false)\n", x, y, depth);
  //printf("fp_x:%d,fp_y:%d\n",fp_x,fp_y);
  //debug
  if(dep_chg)
     depth++;
  printf("depth after judge:%d\n",depth);
  print_vis(visited);//debug
  if(map[y][x] == -3){//end condition
    printf("%d\n",depth-1);//last depth has met the condition but print at next call
    return -1;//pop out this function
  }
  else{
    //put the next level value into queue then pop
    //push if pathable and in range and not visited
    if(dep_chg){//if enter next level
		fp_x = -1;//first push x
		fp_y = -1;
	}
    if(x-1 >= 0 && y >= 0 && x-1 < col && y < row && map[y][x-1] != -1 && !visited[y][x-1]){
      //push into queue
      q_push(x-1, q_x);
      q_push(y, q_y);
      q_end++;
      visited[y][x-1] = true;
	  if(fp_x == -1){
		fp_x = x-1;
		fp_y = y;
	  }
    }
    if(x+1 >= 0 && y >= 0 && x+1 < col && y < row && map[y][x+1] != -1 && !visited[y][x+1]){
      //push into queue
      q_push(x+1, q_x);
      q_push(y, q_y);
      q_end++;
      visited[y][x+1] = true;
      if(fp_x == -1){
        fp_x = x + 1;
        fp_y = y;
      }
    }
    if(x >= 0 && y-1 >= 0 && x < col && y-1 < row && map[y-1][x] != -1 && !visited[y-1][x]){
      //push into queue
      q_push(x, q_x);
      q_push(y-1, q_y);
      q_end++;
      visited[y-1][x] = true;
        if(fp_x == -1){
          fp_x = x;
          fp_y = y - 1;
        }
    }
    if(x >= 0 && y+1 >= 0 && x < col && y+1 < row && map[y+1][x] != -1 && !visited[y+1][x]){
      //push into queue
      q_push(x, q_x);
      q_push(y+1, q_y);
      q_end++;
      visited[y+1][x] = true;
      if(fp_x == -1){
        fp_x = x;
        fp_y = y + 1;
      }
    }
    //don't be too hury to pop new value
    //after visit all these "4" points, we should judge whether I should enter next depth
    //bad pos:bool whether_next = (x != fp_x && y != fp_y) ? false: true;
    printf("fp_x:%d,fp_y:%d\n\n",fp_x,fp_y);//debug
    print_q(q_x,q_y);//debug
    int next_x = q_pop(q_x);
    int next_y = q_pop(q_y);
    q_start++;
    printf("next_x:%d,next_y:%d\n",next_x, next_y);
    print_q(q_x,q_y);//debug
    bool whether_next;
    if(next_x != fp_x || next_y != fp_y)
      whether_next = false;
    else
      whether_next = true;
    if(next_x != -1 && next_y != -1){
      if(!whether_next)
        return bfs(map, next_x, next_y, depth, q_x, q_y, visited, false);
      else
        return bfs(map, next_x, next_y, depth, q_x, q_y, visited, true);
    }
    printf("leave bfs\n");
  }
}
//debug
void print_vis(bool vis[][col]){
  for(int i = 0; i < row; i++){
    for(int j = 0; j < col; j++){
      if(vis[i][j])
        printf("1 ");
      else
        printf("0 ");
    }
    printf("\n");
  }
  printf("\n");
}

int main(int argc, char *argv[]){
  scanf("%d %d",&row, &col);
  //0: pathable
  //-1: handicap
  //-2: start
  //-3: end
  int x_start, y_start;//the start point
  int map[row][col];
  for(int i = 0; i < row; i++){
    for(int j = 0; j < col; j++){
      scanf("%d", &map[i][j]);
      if(map[i][j] == -2){
        x_start = j;
        y_start = i;
      }
    }
  }
  bool visited[row][col];
  for(int i = 0; i < row; i++){
    for(int  j = 0; j < col; j++){
        visited[i][j] = false;
    }
  }
  int depth = 0;
  int max_size = 1;//max_size of queue
  for(int i = (row + col); i >= (col+1); i--){
    max_size *= i;
  }
  for(int i = 1; i <= row; i++){
    max_size /= i;
  }
  //now max_size is C(row+col,row):max way
  max_size *= (row+col);//max_step:walk a diagonal
  int q_x[max_size];
  int q_y[max_size];
  for(int i = 0; i < max_size ; i++){
    q_x[i] = -1;
    q_y[i] = -1;
  }
  visited[y_start][x_start] = true;
  bfs(map, x_start, y_start, depth, q_x, q_y, visited, true);
  return 0;
}

# 舊code

#include<stdio.h>
#include<stdbool.h>
int q_start = 0, q_end = 0/*the index of last value +1*/;
int row, col;
void q_push(int val, int q[]){
  if(q_start <= q_end){
    q[q_end] = val;
  }
  else{
    printf("buffer saturated during push\n");
  }
}

int q_pop(int q[]){
  if(q_start <= q_end){
    return q[q_start];
  }
  else{
    printf("buffer saturated during pop %d\n",q_start);
    return -1;
  }
}

int bfs(int map[][col], int x, int y, int depth, int q_x[], int q_y[], bool visited[][col]){
  if(map[y][x] == -3){//end condition
    printf("%d\n",depth);
    return -1;//pop out this function
  }
  else{
    //put the next level value into queue then pop
    //push if pathable and in range and not visited
    int fp_x = -1;//first push x
    int fp_y = -1;
    if(x-1 >= 0 && y >= 0 && x-1 < col && y < row && map[y][x-1] != -1 && !visited[y][x-1]){
      //push into queue
      q_push(x-1, q_x);
      q_push(y, q_y);
      q_end++;
      visited[y][x-1] = true;
      fp_x = x-1;
      fp_y = y;
    }
    if(x+1 >= 0 && y >= 0 && x+1 < col && y < row && map[y][x+1] != -1 && !visited[y][x+1]){
      //push into queue
      q_push(x+1, q_x);
      q_push(y, q_y);
      q_end++;
      visited[y][x+1] = true;
      if(fp_x == -1){
        fp_x = x + 1;
        fp_y = y;
      }
    }
    if(x >= 0 && y-1 >= 0 && x < col && y-1 < row && map[y-1][x] != -1 && !visited[y-1][x]){
      //push into queue
      q_push(x, q_x);
      q_push(y-1, q_y);
      q_end++;
      visited[y-1][x] = true;
        if(fp_x == -1){
          fp_x = x;
          fp_y = y - 1;
        }
    }
    if(x >= 0 && y+1 >= 0 && x < col && y+1 < row && map[y+1][x] != -1 && !visited[y+1][x]){
      //push into queue
      q_push(x, q_x);
      q_push(y+1, q_y);
      q_end++;
      visited[y+1][x] = true;
      if(fp_x == -1){
        fp_x = x;
        fp_y = y + 1;
      }
    }
    int next_x = q_pop(q_x);
    int next_y = q_pop(q_y);
    q_start++;
    if(next_x != -1 && next_y != -1){
      if(next_x != fp_x && next_y != fp_y)
        return bfs(map, next_x, next_y, depth, q_x, q_y, visited);
      else
        return bfs(map, next_x, next_y, depth+1, q_x, q_y, visited);
    }
  }
}


int main(int argc, char *argv[]){
  scanf("%d %d",&row, &col);
  //0: pathable
  //-1: handicap
  //-2: start
  //-3: end
  int x_start, y_start;//the start point
  int map[row][col];
  for(int i = 0; i < row; i++){
    for(int j = 0; j < col; j++){
      scanf("%d", &map[i][j]);
      if(map[i][j] == -2){
        x_start = j;
        y_start = i;
      }
    }
  }
  bool visited[row][col];
  for(int i = 0; i < row; i++){
    for(int  j = 0; j < col; j++){
        visited[i][j] = false;
    }
  }
  int depth = 0;
  int max_size = 1;//max_size of queue
  for(int i = (row + col); i >= (col+1); i--){
    max_size *= i;
  }
  for(int i = 1; i <= row; i++){
    max_size /= i;
  }
  //now max_size is C(row+col,row):max way
  max_size *= (row+col);//max_step:walk a diagonal
  int q_x[max_size];
  int q_y[max_size];
  for(int i = 0; i < max_size ; i++){
    q_x[i] = -1;
    q_y[i] = -1;
  }
  visited[y_start][x_start] = true;
  bfs(map, x_start, y_start, depth, q_x, q_y, visited);
  return 0;
}

## with debug statement

#include<stdio.h>
#include<stdbool.h>
int q_start = 0, q_end = 0/*the index of last value +1*/;
int row, col;
void q_push(int val, int q[]){
  if(q_start <= q_end){
    q[q_end] = val;
  }
  else{
    printf("buffer saturated during push\n");
  }
}

int q_pop(int q[]){
  if(q_start <= q_end){
    return q[q_start];
  }
  else{
    printf("buffer saturated during pop %d\n",q_start);
    return -1;
  }
}
//debug
void print_vis(bool vis[][col]){
  for(int i = 0; i < row; i++){
    for(int j = 0; j < col; j++){
      if(vis[i][j])
        printf("1 ");
      else
        printf("0 ");
    }
    printf("\n");
  }
  printf("\n");
}
int bfs(int map[][col], int x, int y, int depth, int q_x[], int q_y[], bool visited[][col]){
  //debug
  printf("call bfs(x:%d,y:%d,dep:%d)\n", x, y, depth);
  //debug
  if(map[y][x] == -3){//end condition
    printf("%d\n",depth);
    return -1;//pop out this function
  }
  else{
    //put the next level value into queue then pop
    //push if pathable and in range and not visited
    int fp_x = -1;//first push x
    int fp_y = -1;
    if(x-1 >= 0 && y >= 0 && x-1 < col && y < row && map[y][x-1] != -1 && !visited[y][x-1]){
      //push into queue
      q_push(x-1, q_x);
      q_push(y, q_y);
      q_end++;
      visited[y][x-1] = true;
      fp_x = x-1;
      fp_y = y;
      print_vis(visited);//debug
    }
    if(x+1 >= 0 && y >= 0 && x+1 < col && y < row && map[y][x+1] != -1 && !visited[y][x+1]){
      //push into queue
      q_push(x+1, q_x);
      q_push(y, q_y);
      q_end++;
      visited[y][x+1] = true;
      if(fp_x == -1){
        fp_x = x + 1;
        fp_y = y;
      }
      print_vis(visited);//debug
    }
    if(x >= 0 && y-1 >= 0 && x < col && y-1 < row && map[y-1][x] != -1 && !visited[y-1][x]){
      //push into queue
      q_push(x, q_x);
      q_push(y-1, q_y);
      q_end++;
      visited[y-1][x] = true;
        if(fp_x == -1){
          fp_x = x;
          fp_y = y - 1;
        }
      print_vis(visited);//debug
    }
    if(x >= 0 && y+1 >= 0 && x < col && y+1 < row && map[y+1][x] != -1 && !visited[y+1][x]){
      //push into queue
      q_push(x, q_x);
      q_push(y+1, q_y);
      q_end++;
      visited[y+1][x] = true;
      if(fp_x == -1){
        fp_x = x;
        fp_y = y + 1;
      }
      print_vis(visited);//debug
    }
    //debug
    /*
    printf("q_start = %d\n",q_start);
    printf("q_end = %d\n",q_end);
    for(int i = 0; i < row*col; i++){
        printf("i: %d ",i);
        printf("%d,",q_x[i]);
        printf("%d \n",q_y[i]);
    }
    */
    //debug

    int next_x = q_pop(q_x);
    int next_y = q_pop(q_y);
    q_start++;
    if(next_x != -1 && next_y != -1){
      if(next_x != fp_x && next_y != fp_y)
        return bfs(map, next_x, next_y, depth, q_x, q_y, visited);
      else
        return bfs(map, next_x, next_y, depth+1, q_x, q_y, visited);
    }
    printf("leave bfs\n");
  }
}


int main(int argc, char *argv[]){
  scanf("%d %d",&row, &col);
  //0: pathable
  //-1: handicap
  //-2: start
  //-3: end
  int x_start, y_start;//the start point
  int map[row][col];
  for(int i = 0; i < row; i++){
    for(int j = 0; j < col; j++){
      scanf("%d", &map[i][j]);
      if(map[i][j] == -2){
        x_start = j;
        y_start = i;
      }
    }
  }
  //debug
  printf("x_start = %d\n", x_start);
  printf("y_start = %d\n", y_start);
  //debug
  bool visited[row][col];
  for(int i = 0; i < row; i++){
    for(int  j = 0; j < col; j++){
        visited[i][j] = false;
    }
  }
  int depth = 0;
  for(int i = (row + col); i >= (col+1); i--){
    max_size *= i;
  }
  for(int i = 1; i <= row; i++){
    max_size /= i;
  }
  //now max_size is C(row+col,row):max way
  max_size *= (row+col)/*max_step:walk a diagonal*/;
  int q_x[max_size];
  int q_y[max_size];
  visited[y_start][x_start] = true;
  bfs(map, x_start, y_start, depth, q_x, q_y, visited);//parameters?
  return 0;
}