|
|
发表于 2023-2-6 14:16:21
|
显示全部楼层
我的思路是把每个小迷宫作为有向图里的一个节点，给终点创建一个虚拟的小迷宫（用第 n+1 个节点表示），小迷宫中从左上角到传送门（或终点）的距离作为对应的有向边的边长
先在每个小迷宫上跑 bfs 建图，然后在得到的图上跑 Floyd 最短路（写起来简单）找到终点的最少步数
然而评测记录里根本没有提交通过这道题（难道不登录看不到通过的提交？），而大样例我得到的结果和您的一样（我手工走了一遍，这个结果似乎是正确的？）
- #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号)
狗仔卡
显身卡
楼主
，谁知道什么毛病，我用的是图的最短路径，每个层的左上角为点，能够联通的两个层为边，路径为权值。