提供一个思路：楼主试过从出口找入口？（注意行走都是反的，向上向左） jhq999 发表于 2023-2-5 22:27
提供一个思路：楼主试过从出口找入口？（注意行走都是反的，向上向左）
感觉更麻烦了，效率反而会更慢 我的思路是把每个小迷宫作为有向图里的一个节点，给终点创建一个虚拟的小迷宫（用第 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) return false;
char tile = map;
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 = true;
state_queue_push(queue, node);
while(!state_queue_empty(queue)){
node = state_queue_pop(queue);
char tile = map;
if(tile == '@' || isdigit(tile)){
if(isdigit(tile)){
if(accessible) graph = min(node->state.step_count, graph);
}else{
graph = min(node->state.step_count, graph);
}
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 = 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 = 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 = map != '*';
}
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 == (size_t)-1) fprintf(stream, "%4d ", -1);
else fprintf(stream, "%4zu ", graph);
}
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 == (size_t) -1 || graph == (size_t)-1) continue;
graph = min(graph + graph, graph);
}
if(graph == (size_t)-1) printf("-1\n");
else printf("%zu\n", graph);
return 0;
} dolly_yos2 发表于 2023-2-6 14:16
我的思路是把每个小迷宫作为有向图里的一个节点，给终点创建一个虚拟的小迷宫（用第 n+1 个节点表示），小 ...
还是44{:10_277:} zhangjinxuan 发表于 2023-2-6 18:58
还是44
《符合预期》
毕竟大样例上和您的代码结果一致
严重怀疑题目有问题，至少输入格式是不符合题面描述的 dolly_yos2 发表于 2023-2-6 18:59
《符合预期》
毕竟大样例上和您的代码结果一致
严重怀疑题目有问题，至少输入格式是不符合题面描述的
我还怀疑样例有问题，要不是样例太大，我当场就调出来{:10_306:} zhangjinxuan 发表于 2023-2-6 19:06
我还怀疑样例有问题，要不是样例太大，我当场就调出来
样例很可能有问题，如果题意没理解错的话得到的这个结果（71）是能走出来的 dolly_yos2 发表于 2023-2-6 19:41
样例很可能有问题，如果题意没理解错的话得到的这个结果（71）是能走出来的
但我们不能手算出来，就没有证据去说 本帖最后由 jhq999 于 2023-2-8 17:07 编辑
zhangjinxuan 发表于 2023-2-6 20:24
但我们不能手算出来，就没有证据去说
#include <stdio.h>
#include <stdlib.h>
#define maxnum 0x7fffffff
int m,n,end;
char pt;
typedef struct NODE
{
int len,minpath;
int num;
}node;
node nums;
int num,numend={0},nmpt=0;
int min=maxnum,flag=0;
void pushnum(int a)
{
num=a;
}
int popnum()
{
return num[--nmpt];
}
int exitpoint(char (*p),int i,int j,int k)
{
//char c1=p,c2=p;
char a=p,b=p;
if((j&&k&&(p||p))||(j&&0==k&&p)||(0==j&&k&&p)||(0==j&&0==k))
{
end=i+1;
nums.len=maxnum;
nums.num=j+k;
return 0;
}
return -1;
}
void numpoint(char (*p),int i,int j,int k)
{
if(0==p-'1'])
{
p=1;
}
else
{
char c=p;
if((i!=p-'1')&&((j&&k&&(p||p))\
||(j&&0==k&&p)||(0==j&&k&&p)||(0==j&&0==k)))
{
nums.len=maxnum;
nums.num-'0']=1;
if(j+k<nums.num-'0'])
{
nums.num-'0']=j+k;
nums.num-'0']=i,nums.num-'0']=j,nums.num-'0']=k;
}
}
if(j||k)p=0;
else
{
p='n';
}
}
}
void point(char (*p),int i,int j,int k)
{
if(j)
{
if(k)
{
p=p||p;
}
else
p=p;
}
else if(k)
{
p=p;
}
}
int inidata(char (*p))
{
int i,j,k;
for(i=0; i<n; i+=1)
{
for(j=0; j<m; j+=1)
{
for(k=0; k<m; k+=1)
{
if('.'==p)
point(p,i,j,k);
else if('0'<=p&&'9'>=p)
{
numpoint(p,i,j,k);
if(0==(j||k))j=m,k=m;
}
else if('@'==p)
{
if(-1==exitpoint(p,i,j,k))return -1;
j=m,k=m;
}
}
}
}
return 0;
}
int findminpath()
{
int id;
pushnum(1);
nums.len=0;//////重要，起点赋值为0
while(nmpt)
{
id=popnum();
for(int i=1; i<10; i+=1)
{
if(nums.num)
{
pushnum(i);
nums.num=0;
nums.num=0;
if(nums.len>nums.num+nums.len)
{
nums.len=nums.num+nums.len;
nums.minpath=id;
}
}
}
}
return 0;
}
int main()
{
int i,j,k;
for(i=0;i<10;i+=1)
for(j=0;j<10;j+=1)
nums.num=maxnum;
char t;
FILE *fp=fopen("1.in","rb");
fseek(fp,0,SEEK_END);
int len=ftell(fp),len1=6;
fseek(fp,0,SEEK_SET);
fscanf(fp,"%d%d",&n,&m);
for(i=0; i<n; i+=1)
{
for(j=0; j<m; j+=1)
{
for(k=0; k<m;)
{
len1+=1;
fread(&t,1,1,fp);
if('.'==t)
{
pt=1;
}
else if('*'==t)
{
pt=0;
}
else if(('0'<=t&&'9'>=t)||('@'==t))
{
pt=t;
}
}
}
}
if(-1==inidata(pt))
{
printf("-1\n");
}
else
{
findminpath();
if(maxnum==nums.len)printf("-1");
else
printf("%d\n",nums.len+nums.num);
}
i=end;
while(i>1)
{
int t=i;
i=nums.minpath;
printf("%d %d %d %d %d\n",i,nums.len,nums.num+1,nums.num,nums.num);
}
////////////////////////////////////
fclose(fp);
return 0;
}
71///////@在9层的（0，0）
////////第一个数是层数，第二个数是此层到下层的最短路径，剩下的是层数，行，列
6 25 6 20 5////////6层（0，0）到数字9的最短的那个9的长度，坐标（20，5）
8 14 8 11 3///////8层（0，0）到数字6的最短的那个6的长度，坐标（8，11）
1 32 1 28 4///////1层（0，0）到数字8的最短的那个8的长度，坐标（28，4）
jhq999 发表于 2023-2-8 16:11
RE（运行时错误），非常奇妙，会不会是环境问题{:10_277:}
而且我用C++会CE（编译错误）{:10_291:}
不过，你找到证据啦{:10_277:} 本帖最后由 jhq999 于 2023-2-8 19:15 编辑
zhangjinxuan 发表于 2023-2-8 18:16
RE（运行时错误），非常奇妙，会不会是环境问题
而且我用C++会CE（编译错误）
...
我提交了只有10分，{:5_90:}，谁知道什么毛病，我用的是图的最短路径，每个层的左上角为点，能够联通的两个层为边，路径为权值。
每个层左上角到这个层每个数字的最短路径是唯一的，不是最短的变成石头‘*’
每个左上角到能够到达的数字的路径长就是数字坐标的行和列的和 jhq999 发表于 2023-2-8 19:13
我提交了只有10分，，谁知道什么毛病，我用的是图的最短路径，每个层的左上角为点，能够联通的 ...
{:10_291:}
页:
1
[2]