알고리즘 Jailbreak문제 도저히 모르겠습니다. 고수님 알려주세요
글쓴이: nohhans / 작성시간: 화, 2017/03/07 - 11:25오후
https://www.e-olymp.com/en/problems/6426
이런식으로 작성했는데 50%만 정답으로 나오네요
고수님들 알려주세요
#include <stdio.h> #include <vector> #include <string.h> #include <algorithm> #include <queue> using namespace std; #define mp make_pair #define INF 987654321 int t, n, m, map[105][105], ans; int tx[4] = { 0,0,1,-1 }; int ty[4] = { 1,-1,0,0 }; vector<pair<int, int > > v; priority_queue<pair<int, pair<int, int> > > qq; void init() { char a[102]; while (!qq.empty()) qq.pop(); ans = INF; v.clear(); memset(map, -1, sizeof(map)); scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%s", a); for (int j = 1; j <= m; j++) { if (a[j - 1] == '*') map[i][j] = -1; if (a[j - 1] == '.') map[i][j] = 0; if (a[j - 1] == '#') map[i][j] = 1; if (a[j - 1] == '$') v.push_back(mp(i, j)), map[i][j] = 0; //if ((i == 1 || j == 1 || i == n || j == m) && (map[i][j] != -1)) s.push_back(mp(i, j)); } } } void bfs() { int vis[105][105][2] = { 0, }; priority_queue<pair<pair<int, int>, pair<int, int> > > q; //거리 타입 좌표xy q.push(mp(mp(0, 1), mp(v[0].first, v[0].second))); q.push(mp(mp(0, 2), mp(v[1].first, v[1].second))); vis[v[0].first][v[0].second][0] = 1; vis[v[0].first][v[0].second][1] = 0; vis[v[1].first][v[1].second][0] = 2; vis[v[1].first][v[1].second][1] = 0; while (!q.empty()) { int cx = q.top().second.first; int cy = q.top().second.second; int dis = -q.top().first.first; int type = q.top().first.second; vis[cx][cy][0] = type; vis[cx][cy][1] = dis; q.pop(); for (int i = 0; i < 4; i++) { int nx = cx + tx[i]; int ny = cy + ty[i]; int ndis = dis; if (vis[nx][ny][0] != 0 && vis[nx][ny][0] != type){ qq.push(mp(-(dis + vis[nx][ny][1]), mp(nx, ny))); continue; } if (vis[nx][ny][0] != 0 || map[nx][ny] == -1) continue; if (map[nx][ny] == 1) ndis++; vis[nx][ny][0] = type; vis[nx][ny][1] = ndis; q.push(mp(mp(-ndis, type), mp(nx, ny))); } } return; } int bfs2(int x, int y) { priority_queue<pair<int, pair<int, int> > > q; q.push(mp(0, mp(x, y))); int visit[105][105] = { 0, }; while (!q.empty()) { int cx = q.top().second.first; int cy = q.top().second.second; int dis = -q.top().first; if (cx == 1 || cy == 1 || cx == n || cy == m) return dis; q.pop(); for (int i = 0; i < 4; i++) { int nx = cx + tx[i]; int ny = cy + ty[i]; int ndis = dis; if (map[nx][ny] == -1 || visit[nx][ny] == 1) continue; visit[nx][ny] = 1; if (map[nx][ny] > 0) ndis++; //if (nx == 1 || ny == 1 || nx == n || ny == m) return ndis; q.push(mp(-ndis, mp(nx, ny))); } } return INF; } int bfs3() { int visit[105][105] = { 0, }; while (!qq.empty()) { int cx = qq.top().second.first; int cy = qq.top().second.second; int dis = -qq.top().first; if (cx == 1 || cy == 1 || cx == n || cy == m) return dis; qq.pop(); for (int i = 0; i < 4; i++) { int nx = cx + tx[i]; int ny = cy + ty[i]; int ndis = dis; if (map[nx][ny] == -1 || visit[nx][ny] == 1) continue; visit[nx][ny] = 1; if (map[nx][ny] > 0) ndis++; //if (nx == 1 || ny == 1 || nx == n || ny == m) return ndis; qq.push(mp(-ndis, mp(nx, ny))); } } return INF; } int main() { scanf("%d", &t); while (t--) { init(); bfs(); printf("%d\n", min(bfs2(v[0].first, v[0].second) + bfs2(v[1].first, v[1].second), bfs3())); } }
Forums:
댓글 달기