算法实战4：逃跑问题Escape

问题大致描述：

有个小偷想要抢银行，可是他希望我们帮助他设计逃跑路线

逃跑过程中有如下规则：

（1）经过的路口不能再次走

（2）每次路口只能选择直行或者右转

问：有多少条路可以让小偷顺利回家

假设地图如下，网格状

假设小偷从（0，0）（左下角）开始逃跑，地图右上角（X,Y）是地图边界 ，(x,y)则是小偷的家

输入：

3

3 4 0 0

3 4 1 1 

3 4 1 2

第一行是测试数据条数

第二行是第一组测试数据，分别表示X Y x y

后面分别是第二组，第三组测试数据

方法一：模拟 递归遍历

首先我们知道小偷至少先向上行y个点才能转一次弯就到家，所以起始点逃跑应该是(0,y)

这里我们可以模拟出这个逃跑行为，类似图遍历，就是找出能够到达小偷家的所有路径，这里的图是有向的。

我们可以记录一个访问表表示经过的路口是否经过，没经过，则继续，经过，则返回

我们知道左右都是相对的，如果是自南向北走，执行就是y+1,x不变；如果是自西向东，则直行是x+1,y不变，所以这里需要考虑方向问题。

代码参见如下：

//============================================================================
// Name        : Escape.cpp
// Author      : YLF
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
using namespace std;

enum Direction{
	U,R,D,L
};

void Escape(int i, int j, int X, int Y, int x, int y, Direction dir, bool **visited, int &count);

int main() {

	int caseN;
	cin>>caseN;
	int **arr = new int*[caseN];
	int i = 0;
	for(i=0;i<caseN;i++){
		arr[i] = new int[4];
		cin>>arr[i][0];
		cin>>arr[i][1];
		cin>>arr[i][2];
		cin>>arr[i][3];
	}

	for(i=0;i<caseN;i++){
		int X = arr[i][0], Y = arr[i][1],x=arr[i][2],y=arr[i][3];
		bool **visited = new bool*[Y+1];
		int j=0;
		for(j=0;j<Y+1;j++){
			visited[j] = new bool[X+1];
			int k = 0;
			for(k=0;k<X+1;k++)
				visited[j][k] = false;
		}
		int count = 0;
		//起跑点肯定要在y之上才行，否则绕不到家来了
		Escape(0,y,X, Y, x, y,U,visited,count);
		cout<<count<<endl;
		delete *visited;
	}
	delete []arr;
	return 0;
}

void Escape(int i, int j, int X, int Y, int x, int y, Direction dir, bool **visited, int &count){
	if(i<0 || i>X || j<0 || j>Y)
		return;
	if(visited[j][i])
		return;
	if(i==x && j==y){
		count++;
		return;
	}
	switch(dir){
	case U://up
		visited[j][i] = true;
		Escape(i,j+1,X,Y,x,y,U,visited,count);
		Escape(i+1,j,X,Y,x,y,R,visited,count);
		visited[j][i] = false;
		break;
	case R:
		visited[j][i] = true;
		Escape(i+1,j,X,Y,x,y,R,visited,count);
		Escape(i,j-1,X,Y,x,y,D,visited,count);
		visited[j][i] = false;
		break;
	case D:
		visited[j][i] = true;
		Escape(i,j-1,X,Y,x,y,D,visited,count);
		Escape(i-1,j,X,Y,x,y,L,visited,count);
		visited[j][i] = false;
		break;
	case L:
		visited[j][i] = true;
		Escape(i-1,j,X,Y,x,y,L,visited,count);
		Escape(i,j+1,X,Y,x,y,U,visited,count);
		visited[j][i] = false;
		break;
	}
}
           

5
3 4 0 0
3 4 1 0
3 4 1 1
3 4 2 1
9 9 4 4
1
13
16
16
11356
           

方法二：找规律

这题我们手推几次方向，根据转弯次数可以有序遍历

转弯0次到达：必须是x=0

转弯一次到达：则有Y-y种

转弯两次到达：则有(Y-y)(X-x)

以此类推。。。

表达式太复杂了