题 目 http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=58
思路借鉴 DFS-Deep First Search-深度优先搜索 - 卓华寅的文章 - 知乎
收获总结
1. 重定向输入输出流：freopen( "filename" , "mode" ,stream );
filename:文件名（文件存储在在代码目录下）/文件路径。
mode:操作模式，操作权限，"r"表示“只读访问”、"w"表示“只写访问”、"a"表示“追加写入”。
stream：需要被重定向的文件流。stdin是标准输入流，默认为键盘；stdout是标准输出流，默认为屏幕；stderr是标准错误流，一般把屏幕设为默认。
关闭重定向输入输出流：freopen( "CON","r",stdin );不关闭的话，后续无法使用键盘输入的方式读取数据。
头文件：stdio.h
2.内存空间初始化：void * memset ( void * ptr, int value, size_t num );
eg: memset(buf,0,sizeof(buf));
今天是第一次真正接触 DFS-深度优先算法的题目，虽然在数据结构与算法上已经学习过了，但没有实践，早就忘记了(ノへ￣、)。平时看到这样的题直接忽略，今天终于直面它了。在这之前做的NYOJ 32 组合数完全没有思路，烦躁！后来这道题和迷宫题完全重合，直接套就行，于是让我找回了自信，顺带理解了DFS的迷宫问题。
不过还有一个问题，应该是评测的锅，使用freopen一直是WA，但将迷宫直接以二维数组存储就能够AC了。
WA代码
#include<stdio.h>
;
][],book[][];
int sx,sy,ex,ey,min;
][]={{-,},{,},{,},{,-}};
void dfs(int x,int y,int step)
{
int tx,ty;
if(x==ex&&y==ey)
{
if(min>step)
min=step;
return ;
}
;i<;i++)
{
tx=x+next[i][];
ty=y+next[i][];
||tx>||ty<||ty>) continue;
&&book[tx][ty]==)
{
book[tx][ty]=;
dfs(tx,ty,step+);
book[tx][ty]=;
}
}
}
int main()
{
freopen("in.txt","r",stdin);
;i<;i++)
;j<;j++)
scanf("%d",&num[i][j]);
freopen("CON", "r", stdin);
int n;
scanf("%d",&n);
while(n--)
{
min=max;
scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
book[sx][sy]=;
dfs(sx,sy,);
printf("%d\n",min);
}
;
}
AC代码
#include<stdio.h>
#include<memory.h>
][];
][]={
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,
};
;
][]={{-,},{,},{,},{,-}};
];
void dfs(int x,int y,int step){
if(x==ex && y==ey){
if(min>step) min=step;
return ;
}
;i<;i++){
];
];
||tx<||ty>||ty<) continue;
&&maze[tx][ty]==)
{
book[tx][ty]=;
dfs(tx,ty,step+);
book[tx][ty]=;
}
}
}
int main(){
int n;
scanf("%d",&n);
;i<n;i++){
min=max;
memset(book,,sizeof(book));
scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
book[sx][sy]=;
dfs(sx,sy,);
ans[i]=min;
}
;i<n;i++)
printf("%d\n",ans[i]);
;
}