[백준 16930]달리기

문제 : https://www.acmicpc.net/problem/16930

1)문제분류

-BFS

2)문제 해결 

기본 BFS이지만 주의해야할 점은 

해당방향으로 최대 k만큼 이동하는데 이동하다가, 

#또는 범위를 넘어버리면 바로 탈출하고 (점프가 안되기때문)

다른방향에서 또 탐색   

#include<iostream>

#include<queue>

#include<cstring>

using namespace std;

int n, m, k;

char map[1002][1002];

bool chk[1002][1002];

int sx, sy, ex, ey;

int xrr[4] = { 0,0,1,-1 };

int yrr[4] = { 1,-1,0,0 };

typedef struct Data

{

int x, y, cnt;

}Data;

bool range(int rx, int ry)

{

if (rx<1 || ry<1 || rx>n || ry>m)return false;

else return true;

}

void bfs()

{

queue<Data>pq;

pq.push({ sx,sy,0 });

chk[sx][sy] = true;

while (!pq.empty())

{

Data output = pq.front();

pq.pop();

    

if (output.x == ex && output.y == ey)

{

cout << output.cnt << endl;

return ;

}

for (int i = 0; i < 4; i++)

{

Data  input;

input.x = output.x;

input.y = output.y;

for (int j = 0; j < k; j++)

{

int cx = input.x + xrr[i];

int cy = input.y + yrr[i];

if (range(cx, cy)&& map[cx][cy] == '.')

{

if (chk[cx][cy] == false)

{

chk[cx][cy] = true;

pq.push({ cx,cy,output.cnt + 1 });

}

input.x = cx;

input.y = cy;

  

}

else 

break;

}

}

}

cout << -1 << endl;

return;

}

int main()

{

cin >> n >> m >> k;

for (int i = 1; i <= n; i++)

{

for (int j = 1; j <= m; j++)

{

cin >> map[i][j];

}

}

cin >> sx >> sy >> ex >> ey;

bfs();

}