HDU 5253 연결 파이프 (bfs + 우선 대기 열)
광 수, 일반 우선 대기 열 광 수 와 는 다 르 니 코드 를 구체 적 으로 보 세 요.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int N, M;
struct node {
int x, y, cost;
friend bool operator < (node a, node b) {
return a.cost > b.cost; //
}
};
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
int map[1010][1010];
int vis[1010][1010];
int main() {
int T;
scanf("%d", &T);
int kase;
for(kase = 1; kase <= T; kase++) {
scanf("%d %d", &N, &M);
int i, j;
for(i = 1; i <= N; i++) {
for(j = 1; j <= M; j++) {
scanf("%d", &map[i][j]);
}
}
memset(vis, 0, sizeof(vis));
priority_queue<node> q;
node now, next;
now.x = 1, now.y = 1, now.cost = 0;
q.push(now);
int tot = N * M; // ，
int minc = 0;
printf("Case #%d:
", kase);
while(!q.empty()) {
now = q.top();
q.pop();
if(vis[now.x][now.y] == 1) continue; //
tot--;
vis[now.x][now.y] = 1;
minc += now.cost;
if(tot == 0) {
printf("%d
", minc);
break;
}
for(i = 0; i < 4; i++) {
next.x = now.x + dir[i][0];
next.y = now.y + dir[i][1];
if(next.x < 1 || next.x > N || next.y < 1 || next.y > M || vis[next.x][next.y] == 1) {
continue;
}
next.cost = abs(map[next.x][next.y] - map[now.x][now.y]);
q.push(next);
}
}
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
