알고리즘 > BFS > 장기(1106)

Question

문제 링크

Solving

주의점

장기의 馬는 (+1, +2)로 이동할 수 있기 때문에 자칫 벽의 범위 밖으로 나갈 수도 있다. 이를 방지하는 예외처리를 꼭 한다. (해당 예외를 생각하지 못 하여 마지막 테스트 통과하지 못 했다.)

Code

Colored By Color Scripter™

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76

#include <stdio.h> #include <queue> #pragma warning(disable:4996)   using namespace std;   typedef struct _block {     int x;     int y;     int idx; }block;   queue<block> myQueue; int a, b, min, cnt, map[103][103]; int x[8] = { -2, -1, 1, 2, 2, 1, -1, -2 }; int y[8] = { -1, -2, -2, -1, 1, 2, 2, 1 };   int main() {     FILE *fin = fopen("input.txt", "rt"), *fout = fopen("output.txt", "wt");     block start, end;     int flag = 0;       // input     fscanf(fin, "%d %d", &a, &b);     fscanf(fin, "%d %d %d %d", &start.x, &start.y, &end.x, &end.y);       // init          for (int i = 1; i <= a; i++)     {         for (int j = 1; j <= b; j++)             map[i][j] = 1; // 방문 안 한곳     }       // algo         start.idx = 0;     myQueue.push(start);     map[start.y][start.x] = 2; // 갔던 길은 2로 표시       while (!myQueue.empty())     {         block tmp_block_out;         block tmp_block_in;         tmp_block_out = myQueue.front();         myQueue.pop();         //printf("pop되는 front는 (%d, %d)\n", tmp_block_out.x, tmp_block_out.y);           for (int i = 0; i < 8; i++)         {             // 벽을 만나면...             int posx = tmp_block_out.x+x[i];             int posy = tmp_block_out.y + y[i];                         if (!(posx>0 && posx <= a && posy > 0 && posy <= b)) // !!중요                    continue;             if (map[posx][posy]!=1)                 continue;               tmp_block_in.x = posx;             tmp_block_in.y = posy;             tmp_block_in.idx = tmp_block_out.idx + 1;                            // end를 만났을때              if (posx== end.x && posy == end.y)             {                 fprintf(fout, "%d\n", tmp_block_in.idx);                 return 0;             }             myQueue.push(tmp_block_in);             map[posx][posy] = 2; // 방문 한 곳                     }     } }