麦当劳叔叔的难题
https://www.luogu.com.cn/problem/P1713
前言：
题目本身并不难（虽然是绿题），只要敲代码的时候细心就好
However，蒟蒻表示有一个玄学的问题想请教大家QAQ（请大家移步最后或慢慢看到最后）
题目简述：
给你n×n的地图，以及m个障碍的坐标，起点是(n,1)，终点是(1,n)
要求求出从起点到终点所用时间的最大时间差，即：求最短路径和最长路径的差
思路&代码Code：
题意还是很清晰明了的，用搜索（记忆化！）可以解决
- 方法一：BFS+DFS，先求最短路径，再求最长路径
BFS部分就是裸的板子（我是手写队列党quq）
DFS部分在不加记忆化之前也是裸的板子
注意：在记忆化之前，建议先DFS再BFS，这样bool数组就可以只开一个；但是记忆化之后，因为在DFS中需要用到BFS中求到的最小值，所以是先BFS再DFS，那么记录是否走过的bool数组就需要开两个
#include <bits/stdc++.h>
using namespace std;
int n,m,x,y,last,first;
int f[1001][1001],dis[1001][1001];
bool pd[1001][1001],flag[1001][1001];
int dx[4]={1,0,0,-1}; //搜索顺序真的很坑啊！！在最后会提出
int dy[4]={0,1,-1,0};
struct node { //手写队列
int x,y,st;
} q[100010];
inline void bfs(int xx,int yy) { //bfs求最小值
int front=1,tail=1;
q[front].x=xx;
q[front].y=yy;
q[front].st=0;
while(front<=tail) {
for(register int i=0;i<4;i++) {
int xs=q[front].x+dx[i];
int ys=q[front].y+dy[i];
if(xs>=1&&xs<=n&&ys>=1&&ys<=n&&pd[xs][ys]==false) {
pd[xs][ys]=true;
tail++;
q[tail].x=xs;
q[tail].y=ys;
q[tail].st=q[front].st+1;
if(xs==1&&ys==n) { //到达终点，将最小值记录在first中
first=q[tail].st;
return ;
}
}
}
front++;
}
}
inline void dfs(int xx,int yy) { //dfs求最大值
if(dis[xx][yy]>first&&dis[xx][yy]<f[xx][yy]) return ; //剪枝优化，否则会T第8个点
if(xx==1&&yy==n) {
if(last<dis[xx][yy]) { //更新最大值
last=dis[xx][yy];
for(register int i=1;i<=n;i++) { //记忆化
for(register int j=1;j<=n;j++) {
f[i][j]=dis[i][j];
}
}
}
return ;
}
for(register int i=0;i<4;i++) {
int xs=xx+dx[i];
int ys=yy+dy[i];
if(xs>=1&&xs<=n&&ys>=1&&ys<=n&&flag[xs][ys]==false) { //注意因为先bfs，所以要开两个bool数组记录路径
dis[xs][ys]=dis[xx][yy]+1;
flag[xs][ys]=true;
dfs(xs,ys);
flag[xs][ys]=false;
dis[xs][ys]=0;
}
}
}
int main() {
scanf("%d%d",&n,&m);
for(register int i=1;i<=m;i++) {
scanf("%d%d",&x,&y);
pd[x][y]=flag[x][y]=true; //障碍物直接标记为走过即可，但是不计入步骤数
}
pd[n][1]=flag[n][1]=true; //注意起点要标记为走过
bfs(n,1);
//printf("%d",first);
dfs(n,1);
//printf("%d ",last);
printf("%d",last-first);
return 0;
}
- 方法二：当然了，DFS也是可以同时求最短和最长的
一个DFS也是需要记忆化的，不能也会T掉（这坑代码的第8个点），具体的见代码吧
#include <bits/stdc++.h>
using namespace std;
int n,m,x,y,a[12][12],flag[15][15],first=0x7ffffff,last=-1;
int f[15][15],d[15][15],u[15][15]; //f数组记录当前步数，d数组记录最小步数，u数组记录最大步数
inline int dfs(int now,int x,int y) {
if(x>n||y>n||x<1||y<1||flag[x][y]==1)return 0;
if(now>first&&now<u[x][y])return 0;
/*剪枝，如果当前到达这个点后，步数超过了当前答案最小值或步数小于当前格子的最大步数u[x][y]，return*/
f[x][y]=now;
if(x==1&&y==n) { //更新答案
if(first>now) {
for(register int i=1;i<=n;i++) {
for(register int j=1;j<=n;j++) {
d[i][j]=f[i][j];
}
}
first=now;
}
if(last<now) {
for(register int i=1;i<=n;i++) {
for(register int j=1;j<=n;j++) {
u[i][j]=f[i][j];
}
}
last=now;
}
return 0;
}
flag[x][y]=1;
dfs(now+1,x+1,y); //四个方向
dfs(now+1,x-1,y);
dfs(now+1,x,y+1);
dfs(now+1,x,y-1);
flag[x][y]=0;
f[x][y]=0;
return 0;
}
int main() {
scanf("%d%d",&n,&m);
for(register int i=1;i<=m;i++) {
scanf("%d%d",&x,&y);
flag[x][y]=1;
}
for(register int i=1;i<=n;i++) {
for(register int j=1;j<=n;j++) {
u[i][j]=-1;
d[i][j]=0x7ffffff;
}
}
dfs(1,n,1);
printf("%d",last-first);
return 0;
}
- 方法三：貌似网络流？大家可以自己研究一下（
研究不出来别打我，我看洛谷讨论有说网络流的）
好了，接下来才是本题的重点
问题请教：
在这道题中，如果搜索顺序不同，那么结果也会不同，就会导致得分不同（这..这..）
具体差别：
如下，会T掉第8个点
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
如下，也会T掉第8个点
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
如下，会Wa掉第6个点
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
但是如下，就AC了
int dx[4]={1,0,0,-1};
int dy[4]={0,1,-1,0};
你说顺序不一样T了可以理解，顶多数据问题嘛，毕竟在搜索中有优化搜索顺序这个剪枝
但是Wa我真的就不能理解了，要说代码问题，那其他的怎么就是TLE呢...
而且，有时在其他题目中也会遇到这种情况
来自蒟蒻的求助QAQ
PS：当然了，有时是数据非故意卡，但有时是出题人专门卡你（这就很无奈）