前言

我们在基础模板那篇文章中已经讨论了一个一般性的走迷宫使用的dfs模板，在这里我们依照WolvCTF的ej题目来讲解一下有较多限制的迷宫题目如何做。

ej 题目非迷宫部分的简单介绍

因为在这里我们只讨论迷宫部分的dfs，如果读者想做这道题可以找本人要。（笑）

image-20230320111731465

这里是main函数的部分，可以看到题目的逻辑是这样的，首先输入一个字符串，这个字符串其实就是走迷宫所用的操作，然后经过一个判断，如果判断成功就输出”correct!“，然后用输入作为密钥解密密文，得到flag明文并输出，因此我们其实只需要保证第一个判断能够成功就可以了。

但是这里有一个问题就是，这个判断是走迷宫，但是这个走迷宫的方法不是唯一的，也就是说，我们需要找到所有的路径，然后挨着判断输出是否是真正的flag。

这个判断函数里面是一个走迷宫，这里将迷宫图案贴出来。

0 0 0 0 0 0
0 0 1 1 0 0
0 0 1 0 0 0
0 0 1 0 0 1
0 0 0 1 2 0
2 0 0 0 0 2

这里有三种情况，分别是0 ,1,2。

要求是这样的，0是可以走的，并且没有限制，起点是（0,0），终点也是（0,0）。

1是可以选择走或者不走，但是如果要走的话有限制，就是从1之前的位置来到1时选择的方向，从1之紧接着还要再走一次。举个例子，从坐标（2,1）走到（2,2）这个是1 的位置，是向右走，那么从（2,2）还要再向右走一次走到（2,3），其他方向不可以走。

2是必须要走的，走2的时候也有限制，从2之前来的最近的两次操作必须是一样的，在2这个位置必须拐弯，拐弯之后紧接着的两次操作也必须是一样的。比如如果从（2,4）这个位置要走到（4,4）这个位置，必须是往下走两个，然后拐弯，向左再走两个位置（这个和（4,3）坐标的1的限制并不冲突）

知道了迷宫的走法后，我们就可以来写dfs走迷宫了。

代码及其解析

#include<iostream>
using namespace std;
int map[6][6]={
  0,0,0,0,0,0,
  0,0,1,1,0,0,
  0,0,1,0,0,0,
  0,0,1,0,0,1,
  0,0,0,1,2,0,
  2,0,0,0,0,2
};
int dx[]={-1,1,0,0};//x的变化量
int dy[]={0,0,-1,1};//y的变化量
bool r[6][6];//记录是否走过这个位置
int v2=3;//记录还有多少个2的点需要走
char path[50];//记录路径
int length=0;//记录路径长度
char op[]={'u','d','l','r'};//表示操作 
bool check(int x,int y){//检查点的合法性
	if(x==0&&y==0&&v2==0)return true;
	if(x>=0&&x<=5&&y>=0&&y<=5){
		if(r[x][y]==0)return true;
	}
	return false;
}
int ans=0;//记录有多少条路径是成功的
void dfs(int x,int y,int move){//move  ->   0->u  1->d  2->l  3->r
    							//move这个参数记录走到(x,y)这个点的操作是什么
	if(x==0&&y==0&&v2==0){  //首先判断是否成功，v2记录还有多少2没有走
		ans++;
		
		for(int i=0;i<length;i++){
			cout<<path[i];
		}
		cout<<" "<<ans;
		cout<<endl;
		return; 
	}
	if(map[x][y]==2){//判断是不是2 
	
		for(int i=0;i<4;i++){//我们要往4个方向都要走，这里其实有一个问题，
            				//就是我没有判断拐弯，因为这个迷宫是固定的
            				//所以拐弯不需要判定，一定会拐弯
		int qx=x+dx[i]+dx[i];//对x进行两次变化，要走两步一样的
		int qy=y+dy[i]+dy[i];//对y也进行同样的操作
			if(check(qx,qy)&&check(qx-dx[i],qy-dy[i])&&(path[length-1]==path[length-2])){ //前两个是分别判断要走的两个点是否合法
                			//第三个是判断2之前的两次操作必须一样
				//cout<<qx<<" "<<qy<<endl;
				path[length]=op[i]; //这要走两步，因此要写两遍
				length++;
				path[length]=op[i];
				length++;
				r[qx][qy]=1;       //标记是否走过
				r[qx-dx[i]][qy-dy[i]]=1;
				dfs(qx,qy,i);
				r[qx-dx[i]][qy-dy[i]]=0;//回溯
				r[qx][qy]=0;
				length--;
				path[length]=0;
				length--;
				path[length]=0;
			}
		}
	return;			//别忘了返回！
	}
	if(map[x][y]==1){
		int qx=x+dx[move];		//要和上一次操作一样，move这个参数就是为了这里准备的
		int qy= y+dy[move];	
		if(check(qx,qy)){
			//cout<<qx<<" "<<qy<<endl;
			if(map[qx][qy]==2)v2--;  //这里是一个关键的地方，如果即将要走的点是2
            						//就要让v2自减
			path[length]=op[move];
			length++;
			r[qx][qy]=1;
			dfs(qx,qy,move);
			r[qx][qy]=0;		//回溯！
			length--;
			path[length]=0;
			if(map[qx][qy]==2)v2++;
		} 
		return;				//别忘了返回！
	}
	
	for(int i=0;i<4;i++){		//如果是0的话就走这个循环
		int qx=x+dx[i];
		int qy=y+dy[i];
		if(check(qx,qy)){
			if(map[qx][qy]==2)v2--;
			path[length]=op[i];
			length++;
			r[qx][qy]=1;
		//	cout<<x<<" "<<y<<"key"<<qx<<" "<<qy<<endl;
			dfs(qx,qy,i);
			r[qx][qy]=0;    //回溯
			length--;
			path[length]=0;
			if(map[qx][qy]==2)v2++;
		}
	}
	
	
	
}

int main(){
	for(int i=0;i<=5;i++){
		for(int j=0;j<=5;j++){
			cout<<map[i][j];
		}
		cout<<endl;
	}
	r[0][0]=1;	//首先把（0,0）这个位置标记为走过，防止回走
	dfs(0,0,0);//调用dfs，第三个参数可以随便写
	cout<<ans;
	return 0;
}

在这里的dfs里面我们在要先将特殊的位置进行判断，之后再判断不特殊的位置

可以看到这里的代码套用的完全是上一篇文章的模板，即使是有1和2的限制，也逃脱不开模板

102个输出！

dddddrrrrruuuuulddddlluuuull 1
dddddrrrrruuuuulddddllluuuul 2
dddddrrrrruuuuulddddllluurruulll 3
dddddrrrrruuuuulddddlllurruuulll 4
dddddrrrrruuuuulddddlllurrulluul 5
dddddrrrrruuuuullddrddlluuuull 6
dddddrrrrruuuuullddrddllluuuul 7
dddddrrrrruuuululddrddlluuuull 8
dddddrrrrruuuululddrddllluuuul 9
dddddrrrrruuuuldddlluuuull 10
dddddrrrrruuuuldddllluuuul 11
dddddrrrrruuuuldddllluurruulll 12
dddddrrrrruuuuldddlllurruuulll 13
dddddrrrrruuuuldddlllurrulluul 14
dddddrrrrruuulddlluuuull 15
dddddrrrrruuulddllluuuul 16
dddddrrrrruuulddllluuurrrullll 17
dddddrrrrruuulddllluuurrrrulllll 18
dddddrrrrruuulddllluurruulll 19
dddddrrrrruuulddlllurruuulll 20
dddddrrrrruuulddlllurrulluul 21
dddddrrrrruuulddlllurrullurrrullll 22
dddddrrrrruuulddlllurrullurrrrulllll 23
ddrurrrdddlllulddrrrrruuuuulllll 24
ddrdlddrrrrruuuuulddddlluuuull 25
ddrdlddrrrrruuuuullddrddlluuuull 26
ddrdlddrrrrruuuululddrddlluuuull 27
ddrdlddrrrrruuuuldddlluuuull 28
ddrdlddrrrrruuulddlluuuull 29
ddrrrrddlllulddrrrrruuuuuldlllul 30
ddrrrrddlllulddrrrrruuuuulllll 31
ddrrrrddlllulddrrrrruuuulullll 32
ddrrrrddlllulddrrrrruuuullllul 33
drddlddrrrrruuuuulddddlluuuull 34
drddlddrrrrruuuuullddrddlluuuull 35
drddlddrrrrruuuululddrddlluuuull 36
drddlddrrrrruuuuldddlluuuull 37
drddlddrrrrruuulddlluuuull 38
drdldddrrrrruuuuulddddlluuuull 39
drdldddrrrrruuuuulddddlllurruuulll 40
drdldddrrrrruuuuullddrddlluuuull 41
drdldddrrrrruuuululddrddlluuuull 42
drdldddrrrrruuuuldddlluuuull 43
drdldddrrrrruuuuldddlllurruuulll 44
drdldddrrrrruuulddlluuuull 45
drdldddrrrrruuulddlllurruuulll 46
drdrrrddlllulddrrrrruuuuulllll 47
drdrrrddlllulddrrrrruuuulullll 48
drrrrdddllluuldddrrrrruuuuulllll 49
drrrrdddlllulddrrrrruuuuulllll 50
drrrrdddlllurrullldddrrrrruuuuulllll 51
rddddrrruuuurdddddllllluuuuu 52
rddddrrruuurddddllllluuuuu 53
rddddrrruuluurdrddddllllluuuuu 54
rddddrrruuluurrdddddllllluuuuu 55
rddddrrruurdddllllluuuuu 56
rddrrdlldrrruuuurdddddllllluuuuu 57
rddrrdlldrrruuurddddllllluuuuu 58
rddrrdlldrrruurdddllllluuuuu 59
rdrrrurdddddllllluurdrrruulllluu 60
rdrrrrddddllllluurdrrruulllluu 61
rrddddrruuuurdddddllllluuuuu 62
rrddddrruuuurdddddllllluuurulu 63
rrddddrruuuurdddddllllluuruulu 64
rrddddrruuuurdddddllllluuruluu 65
rrddddrruuurddddllllluuuuu 66
rrddddrruuurddddllllluuurulu 67
rrddddrruuurddddllllluuruulu 68
rrddddrruuurddddllllluuruluu 69
rrddddrruuluurdrddddllllluuuuu 70
rrddddrruuluurdrddddllllluuurulu 71
rrddddrruuluurdrddddllllluuruulu 72
rrddddrruuluurdrddddllllluuruluu 73
rrddddrruuluurrdddddllllluuuuu 74
rrddddrruuluurrdddddllllluuurulu 75
rrddddrruuluurrdddddllllluuruulu 76
rrddddrruuluurrdddddllllluuruluu 77
rrddddrruurdddllllluuuuu 78
rrddddrruurdddllllluuurulu 79
rrddddrruurdddllllluuruulu 80
rrddddrruurdddllllluuruluu 81
rrrdddlldrrruuuurdddddllllluuuuu 82
rrrdddlldrrruuuurdddddllllluuurulu 83
rrrdddlldrrruuurddddllllluuuuu 84
rrrdddlldrrruuurddddllllluuurulu 85
rrrdddlldrrruurdddllllluuuuu 86
rrrdddlldrrruurdddllllluuurulu 87
rrrddllddrrruuuurdddddllllluuuuu 88
rrrddllddrrruuurddddllllluuuuu 89
rrrddllddrrruurdddllllluuuuu 90
rrrrdllldddrrruurdddllllluuuuu 91
rrrrdllldrrdlldrrruurdddllllluuuuu 92
rrrrdrddddllllluurdrrruulllulu 93
rrrrdrddddllllluurdrrruulllluu 94
rrrrrdddddllllluuurddrrruuullllu 95
rrrrrdddddllllluuurrrdlldrrruuullllu 96
rrrrrdddddllllluurdrrruuullldluu 97
rrrrrdddddllllluurdrrruuullllu 98
rrrrrdddddllllluurdrrruulllulu 99
rrrrrdddddllllluurdrrruulllluu 100
rrrrrdlllldddrrruurdddllllluuuuu 101
rrrrrdlllldrrdlldrrruurdddllllluuuuu 102

笔者挨着从第一个开始测试，终于到第92个的时候测试成功了，flag出现了

www,运气真差,www