자율 주행 알고리즘 개발 문제 코드

자율 주행 알고리즘 개발 문제 코드

#include <iostream>

#include <queue>

using namespace std;

int H;//세로크기

int W;//가로크기

char map[500][510];//지도

int visit[500][510];

int ans = 2100000000;

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

void input_data(){

int i;

cin >> H >> W;

for(i=0 ; i<H ; i++){

cin >> map[i];

}

}

class Pos{

public:

int x;

int y;

int cnt;

};

// void dfs(Pos pos, int cnt){

// if(pos.x == H-1 && pos.y == W-1){

// ans = ans < cnt ? ans : cnt;

// return;

// }

// visit[pos.x][pos.y] = 1;

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

// Pos newPos;

// newPos.x = pos.x+dir[i][0];

// newPos.y = pos.y+dir[i][1];

// if(visit[newPos.x][newPos.y] == 1){continue;}

// if(map[newPos.x][newPos.y] == 'X'){continue;}

// if(newPos.x < 0 || newPos.y < 0 || newPos.x >= H || newPos.y >= W){continue;}

// dfs(newPos, cnt+1);

// visit[newPos.x][newPos.y] =0;

// }

// }

void bfs(Pos p){

queue<Pos> q;

visit[p.x][p.y] = 1;

q.push(p);

while(!q.empty()){

Pos pos = q.front();

q.pop();

if(pos.x == H-1 && pos.y == W-1){

ans = pos.cnt;

return;

}

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

Pos newPos;

newPos.x = pos.x+dir[i][0];

newPos.y = pos.y+dir[i][1];

newPos.cnt = pos.cnt + 1;

if(visit[newPos.x][newPos.y] == 1){continue;}

if(map[newPos.x][newPos.y] == 'X'){continue;}

if(newPos.x < 0 || newPos.y < 0 || newPos.x >= H || newPos.y >= W){continue;}

visit[newPos.x][newPos.y] = 1;

q.push(newPos);

}

}

}

int main(){

input_data();

// 코드를 작성하세요

Pos pos;

pos.x = 0;

pos.y = 0;

pos.cnt = 0;

bfs(pos);

if(ans == 2100000000) ans=-1;

cout << ans << endl;

return 0;

}