麦当劳叔叔的难题

发表于 更新于 分类于 
1
这篇题解应该是我征战TG以来第一篇题解，特此纪念。

这道题是个搜索好题，有很多种做法，大体题意就是走迷宫（可以上下左右走），大小为n*n，其中有m个障碍，问你从左下角到右上角的最大步数与最小步数之差。

我们分开来看，最小步数的话，bfs一遍就行了，最大步数的话，写个dfs试试看，万一就卡时间过了呢（这种思想很危险，NOIP千万不能这么想）。。。

bfs的思路：两个队列qx,qy分别存x,y坐标，pd[][]用来判重，dis[i][j]表示到(i,j)的最少步数，应该比较好懂。

dfs的思路：
①：直接爆搜，具体解释见代码一。

②：记忆化搜索，为了不超时，记忆化是个好东西，同样，pd[][]判重，但dis[i][j]表示到(i,j)的步数(是个临时变量，要回溯)，M[][]表示到(i,j)的最大步数(基本确定，只有最后的最大值修改时才会变)，具体解释见代码二。

给各位读者一段话：你的水平不取决于你解决了多少个题，而是取决于你是如何思考的。当你试图去解决一个问题时，你应该先独立思考。如果你实在没有思路，那么你应该去一点一点的读别人的题解，而不是一次性都读完，尽可能确保能有更多的部分是你自己做出来的。之后，仔细思考下，为什么你会想不出来依赖于题解解决的那些部分。千万别抄别人的代码，每个人都有他独特的解题理解方式。

所以说……有思路就不要再看我的代码了。

附件：

代码一（90Pts） 有一个点TLE，原因是dfs直接爆搜。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
int n,m,minn,maxx;//minn为最小步数，maxx为最大步数 
bool Map[20][20],pd[20][20],vis[20][20];//Map[][]用来存那个点为障碍，其他变量上面有解释，vis[][]和pd[][]一个用处 
int dis[20][20];
queue <int> qx,qy;
namespace DY {
    void bfs() {
        qx.push(n);//从左下角出发 
        qy.push(1);
//		dis[1][1]=1;
        pd[n][1]=1;
        while(!qx.empty()) {
            int xx=qx.front(),yy=qy.front();
            qx.pop(); qy.pop();
            for(int i=0; i<4; i++) {
                int nowx=xx+dx[i],nowy=yy+dy[i];//向四周扩展 
                if(nowx>0&&nowy>0&&nowx<=n&&nowy<=n&&Map[nowx][nowy]==0&&pd[nowx][nowy]==0) {
                    if(nowx==1&&nowy==n) {//到达右上角，因为bfs的第一个结果一定是最优解，所以可以节省时间 
                        minn=dis[xx][yy]+1;
                        return ;
                    }
                    qx.push(nowx); qy.push(nowy);//把新点入队 
                    pd[nowx][nowy]=1;
                    dis[nowx][nowy]=dis[xx][yy]+1;
                }
            }
        }
    }
    void dfs(int xx,int yy,int Dis) {//爆搜 
        if(xx==1&&yy==n) {//到达右上角 
            maxx=max(maxx,Dis);//取最大值 
            return ;
        }
        for(int i=0; i<4; i++) {
            int nowx=xx+dx[i],nowy=yy+dy[i];
            if(nowx>0&&nowy>0&&nowx<=n&&nowy<=n&&Map[nowx][nowy]==0&&vis[nowx][nowy]==0) {
                vis[nowx][nowy]=1;
                dfs(nowx,nowy,Dis+1);//往下一个点搜 
                vis[nowx][nowy]=0;//回溯 
            }
        }
    }
    void main() {
        scanf("%d%d",&n,&m);
        for(int i=1; i<=m; i++) {
            int x,y;
            scanf("%d%d",&x,&y);
            Map[x][y]=1;//记录障碍 
        }
        bfs();//广搜求最少步数 
        vis[n][1]=1;
        dfs(n,1,0);//深搜求最大步数 
        printf("%d",maxx-minn);
    }
};
int main() {
    DY::main();
    return 0;
}

代码二（100Pts）dfs变成了记忆化搜索，节省时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define re register
using namespace std;
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
int n,m,minn,maxx;
bool Map[20][20],pd[20][20];//变量解释见上文或代码一 
int dis[20][20],M[20][20];
queue <int> qx,qy;
namespace DY {
	inline void control() {//将f[][]赋值给M[][] 
		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				M[i][j]=dis[i][j];
	}
	inline void bfs() {//广搜解释见代码一 
		qx.push(n); qy.push(1);
		pd[n][1]=1;
		while(!qx.empty()) {
			int xx=qx.front(),yy=qy.front();
			qx.pop(); qy.pop();
			for(re int i=0; i<4; i++) {
				int nowx=xx+dx[i],nowy=yy+dy[i];
				if(nowx>0&&nowy>0&&nowx<=n&&nowy<=n&&(!Map[nowx][nowy])&&(!pd[nowx][nowy])) {
					if(nowx==1&&nowy==n) {
						minn=dis[xx][yy]+1;
						return ;
					}
					dis[nowx][nowy]=dis[xx][yy]+1;
					pd[nowx][nowy]=1;
					qx.push(nowx); qy.push(nowy);
				}
			}
		}
	}
	inline void dfs(int xx,int yy) {//记忆化深搜 
		if(dis[xx][yy]>minn&&dis[xx][yy]<M[xx][yy]) return ;//剪枝，如果到这个点的步数已经比最小值大了，但是却没有以前经过此点的步数多，再见。 
		if(xx==1&&yy==n) {//到达右上角 
			if(dis[xx][yy]>maxx) {//取最大值 
				maxx=dis[xx][yy];
				control();//此函数用来更新M[][]即把当前的f[][]赋值给M[][] 
			}
			return ;
		}
		for(int i=0; i<4; i++) {
			int nowx=xx+dx[i],nowy=yy+dy[i];
			if(nowx>0&&nowy>0&&nowx<=n&&nowy<=n&&(!Map[nowx][nowy])&&(!pd[nowx][nowy])) {
				pd[nowx][nowy]=1;
				dis[nowx][nowy]=dis[xx][yy]+1;
				dfs(nowx,nowy);//搜下一个点 
				pd[nowx][nowy]=0;//回溯 
				dis[nowx][nowy]=0;
			}
		}
	}
	inline void main() {
		scanf("%d%d",&n,&m);
		for(re int i=1; i<=m; i++) {
			int x,y;
			scanf("%d%d",&x,&y);
			Map[x][y]=1;//记录障碍 
		}
		bfs();//广搜求最少步数 
		memset(pd,0,sizeof(pd));//清零 
		memset(dis,0,sizeof(dis));
		pd[n][1]=1;
		dfs(n,1);//深搜求最大步数 
//		cout<<maxx<<endl<<minn<<endl;
		printf("%d",maxx-minn);
	}	
};
int main() {
	DY::main();
	return 0;
}

祝各位OIer(Of course including me)

RP++;