#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
static inline size_t min(size_t lhs, size_t rhs){ return lhs < rhs ? lhs : rhs; }
struct location{
size_t x;
size_t y;
};
struct state{
struct location location;
size_t step_count;
};
struct state_node{
struct state state;
struct state_node* next;
};
struct state_queue{
struct state_node* head;
struct state_node* tail;
};
struct possible_location{
struct location location;
bool available;
};
void state_queue_init(struct state_queue* queue){
queue->head = queue->tail = NULL;
}
bool state_queue_empty(const struct state_queue* queue){
return queue->head == NULL;
}
void state_queue_push(struct state_queue* queue, struct state_node* node){
if(queue->head == NULL) queue->head = node;
else queue->tail->next = node;
node->next = NULL;
queue->tail = node;
}
struct state_node* state_queue_pop(struct state_queue* queue){
struct state_node* result = queue->head;
queue->head = result->next;
return result;
}
void state_queue_clear(struct state_queue* queue){
while(!state_queue_empty(queue)){
struct state_node* node = state_queue_pop(queue);
free(node);
}
}
bool check_destination(const struct location* location, const char* map, bool* visited, const size_t m){
if(location->x >= m || location->y >= m) return false;
if(visited[location->x * m + location->y]) return false;
char tile = map[location->x * m + location->y];
if(tile == '*') return false;
return true;
}
struct state_node* state_node_copy(const struct state_node* source){
struct state_node* node = malloc(sizeof(struct state_node));
node->next = NULL;
node->state.location = source->state.location;
node->state.step_count = source->state.step_count;
return node;
}
void walk_maze(
size_t* graph, const char* map, const bool* accessible,
const size_t n, const size_t m, bool* visited, struct state_queue* queue
){
memset(visited, 0, sizeof(bool) * m * m);
struct state_node* node = malloc(sizeof(struct state_node));
node->next = NULL;
node->state.location.x = 0;
node->state.location.y = 0;
node->state.step_count = 0;
visited[0] = true;
state_queue_push(queue, node);
while(!state_queue_empty(queue)){
node = state_queue_pop(queue);
char tile = map[node->state.location.x * m + node->state.location.y];
if(tile == '@' || isdigit(tile)){
if(isdigit(tile)){
if(accessible[tile - '1']) graph[tile - '1'] = min(node->state.step_count, graph[tile - '1']);
}else{
graph[n] = min(node->state.step_count, graph[n]);
}
free(node);
continue;
}
node->state.step_count += 1;
node->state.location.x += 1;
if(check_destination(&node->state.location, map, visited, m)){
state_queue_push(queue, state_node_copy(node));
visited[node->state.location.x * m + node->state.location.y] = true;
}
node->state.location.x -= 1;
node->state.location.y += 1;
if(check_destination(&node->state.location, map, visited, m)){
state_queue_push(queue, node);
visited[node->state.location.x * m + node->state.location.y] = true;
}else{
free(node);
}
}
}
void walk(size_t* graph, const char* map, const size_t n, const size_t m){
struct state_queue queue;
state_queue_init(&queue);
bool* visited = malloc(sizeof(bool) * m * m);
bool* accessible = malloc(sizeof(bool) * n);
for(size_t i = 0, offset = 0; i < n; i++, offset += m * m){
accessible[i] = map[offset] != '*';
}
for(size_t i = 0; i < n; i++){
walk_maze(graph + i * (n + 1), map + i * m * m, accessible, n, m, visited, &queue);
}
free(visited);
free(accessible);
}
void print_graph(const size_t* graph, const size_t n, FILE* stream){
for(size_t i = 0, offset = 0; i <= n; i++){
for(size_t j = 0; j <= n; j++, offset++){
if(graph[offset] == (size_t)-1) fprintf(stream, "%4d ", -1);
else fprintf(stream, "%4zu ", graph[offset]);
}
fputc('\n', stream);
}
}
int main(){
size_t n, m;
scanf("%zu%zu", &n, &m);
char* map = malloc(n * m * m);
for(size_t i = 0, offset = 0; i < n; i++){
for(size_t j = 0; j < m; j++, offset += m){
char c;
do{
c = getchar();
}while(!isdigit(c) && c != '.' && c != '@' && c != '*');
ungetc(c, stdin);
fread(map + offset, m, 1, stdin);
}
}
size_t* graph = malloc(sizeof(size_t) * (n + 1) * (n + 1));
memset(graph, -1, sizeof(size_t) * (n + 1) * (n + 1));
walk(graph, map, n, m);
//print_graph(graph, n, stderr);
for(size_t k = 0; k <= n; k++) for(size_t i = 0; i <= n; i++) for(size_t j = 0; j <= n; j++){
if(graph[i * (n + 1) + k] == (size_t) -1 || graph[k * (n + 1) + j] == (size_t)-1) continue;
graph[i * (n + 1) + j] = min(graph[i * (n + 1) + k] + graph[k * (n + 1) + j], graph[i * (n + 1) + j]);
}
if(graph[n] == (size_t)-1) printf("-1\n");
else printf("%zu\n", graph[n]);
return 0;
}
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2023-2-5 22:27:55
显身卡
楼主
，谁知道什么毛病，我用的是图的最短路径，每个层的左上角为点，能够联通的两个层为边，路径为权值。