-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
dx와 dy 배열 순서에 관해 질문이 있습니다!
21.10.04 11:28 작성 조회수 142
0
dx와 dy안에 배열 순서를 {int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
이런식으로 바꿨는데 왜 답도 같이 바뀌는 건가요??
DFS로 계속 돌면 어차피 경로는 똑같이 가져야하는게 아닌가요???
답변을 작성해보세요.
0
ismy123
질문자2021.10.07
배운걸 활용해서 코드를 짜봤는데 dx dy의 배열순서가 달라지면 값이 다르게 나와서 질문드립니다~!
이런 경우는 왜 그런지 모르겠어요,,,,
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<vector<int>> map(201, vector<int>(201, 1));
vector<vector<int>> visited(201, vector<int>(201, 0));
vector<pair<int, int>> cctvx[4], cctvy[5];
int res = INT_MAX, n;
int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
void DFS(int x, int y,int timer,int cctvi) {
int xx, yy;
if (x == n && y == n) {
res = min(timer, res);
}
else {
while (cctvx[cctvi][0].first <= x && x <= cctvx[cctvi][0].second&&cctvy[cctvi][0].first <= y && y <= cctvy[cctvi][0].second) {
timer++;
cctvi++;
if (cctvi == 4)
cctvi = 0;
}
for (int i = 0; i < 4; i++) {
xx = x + dx[i];
yy = y + dy[i];
if (xx<1 || xx>n || yy<1 || yy>n) continue;
if (map[xx][yy] == 0 && visited[xx][yy] == 0){
visited[xx][yy] = 1;
timer++;
cctvi++;
if (cctvi == 4)
cctvi = 0;
DFS(xx, yy,timer,cctvi);
visited[xx][yy] = 0;
}
}
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> map[i][j];
}
}
cctvx[0].push_back(make_pair(0, n / 4));
cctvx[1].push_back(make_pair(n - (n / 4), n));
cctvx[2].push_back(make_pair(n - (n / 4), n));
cctvx[3].push_back(make_pair(0, n / 4));
cctvy[0].push_back(make_pair(0, n / 4));
cctvy[1].push_back(make_pair(0, n/4));
cctvy[2].push_back(make_pair(n - (n / 4), n));
cctvy[3].push_back(make_pair(n - (n / 4), n));
visited[1][1] = 1;
DFS(1,1,0,0);
if (res == INT_MAX) {
cout << -1;
return 0;
}
else
cout << res;
return 0;
}
답변 1