Fzu 2186 샤오밍의 미로(상태 압축 dp + bfs)
해결:
인터넷에 있는 다른 사람들의 코드를 보고서야 어떻게 하는지 알게 되었다.먼저 BFS로 각 점에서 다른 점까지의 거리, 즉 각 보물 간의 최단길(기점 포함)을 계산한 다음에 상압 최단길 처리를 한다.구체적인 방법: 상태 압축, 1은 현재의 보물이 이미 획득되었음을 의미하고, 0은 현재의 보물이 아직 획득하지 못했다는 것을 의미한다.dp[st][i]는 현재 보물이 st인 상황에서 종점이 i임을 나타낸다.그럼 다음에 도착할 점 j를 일일이 열거해 보세요.결과 상태 이동 공식은 dp[st|(1<
참고:
두 가지 상황의 기점은 마이너스이고 보물 간에 연결이 되지 않으며 이 두 가지 상황은 -1을 출력해야 한다.보물이 존재하고 보물이 원점에 있으면 0을 출력해야 한다.
AC 코드
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <queue>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 105;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = { 0,-1, 0, 1};
struct Point {
int x, y;
Point() {}
Point(int _x, int _y) {
x = _x, y = _y;
}
}poi[20];
struct Node {
int x, y, dist;
Node() {}
Node(int _x, int _y, int _dist) {
x = _x; y = _y; dist = _dist;
}
};
int grid[N][N], dist[20][20], dp[(1<<12)][20];
int n, m, tot;
bool vis[N][N];
int bfs(int star, int end) {
memset(vis, false, sizeof(vis));
queue<Node> que;
que.push(Node(poi[star].x, poi[star].y, 0));
int step, x, y;
while(!que.empty()) {
Node front = que.front();
que.pop();
if(front.x == poi[end].x && front.y == poi[end].y)
return front.dist;
for(int i = 0; i < 4; i++) {
x = front.x + dx[i];
y = front.y + dy[i];
if(x < 1 || x > n || y < 1 || y > m || grid[x][y] < 0) continue;
if(!vis[x][y]) {
vis[x][y] = true;
step = front.dist + 1;
que.push(Node(x, y, step));
}
}
}
return -1;
}
bool getDist() {
memset(dist, 0, sizeof(dist));
for(int i = 0; i <= tot; i++) {
for(int j = 0; j < i; j++) {
dist[i][j] = dist[j][i] = bfs(i, j);
if(dist[i][j] == -1) return false;
}
}
return true;
}
int tsp() {
memset(dp,INF,sizeof(dp));
dp[1][0] = 0;
int end = (1<<(tot+1)) - 1;
for (int st=0; st <=end; st++)
for(int i=0; i <= tot; i++)
for(int j=0;j <= tot; j++) {
if (i == j) continue;
if ((1 << i) & st == 0 || (1 << j) & st == 1) continue;
if (dp[st][i] == INF) continue;
dp[st|(1<<j)][j]=min(dp[st|(1<<j)][j],dp[st][i]+dist[i][j]);
}
int ans = INF;
for (int i=1;i<=tot;i++)
ans=min(ans,dp[end][i]+dist[i][0]);
return ans;
}
int main() {
while(scanf("%d%d", &n, &m) != EOF) {
tot = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
scanf("%d", &grid[i][j]);
if(i + j == 2) continue;
if(grid[i][j] > 0)
poi[++tot] = Point(i, j);
}
}
if(tot == 0) {
puts("0");
continue;
}
poi[0] = Point(1, 1);
if(grid[1][1] < 0 || !getDist()) {
puts("-1");
continue;
}
printf("%d
", tsp());
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[FZU] 2082 통행료 나무 사슬 분할 템플릿 문제전송문:【FZU】2082 통행료 전송문: 나체의 나무 사슬로 나뉜다. 코드는 다음과 같습니다....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.