标题：穿越雷区
X星的坦克战车很奇怪，它必须交替地穿越正能量辐射区和负能量辐射区才能保持正常运转，否则将报废。 某坦克需要从A区到B区去（A，B区本身是安全区，没有正能量或负能量特征），怎样走才能路径最短？
已知的地图是一个方阵，上面用字母标出了A，B区，其它区都标了正号或负号分别表示正负能量辐射区。 例如：
A + - + - - + - - + - + + + - + - + - + B + - + -坦克车只能水平或垂直方向上移动到相邻的区。
数据格式要求：
输入第一行是一个整数n，表示方阵的大小， 4<=n<100 接下来是n行，每行有n个数据，可能是A，B，+，-中的某一个，中间用空格分开。 A，B都只出现一次。
要求输出一个整数，表示坦克从A区到B区的最少移动步数。 如果没有方案，则输出-1
例如： 用户输入： 5
A + - + - - + - - + - + + + - + - + - + B + - + -则程序应该输出： 10
资源约定： 峰值内存消耗 < 512M CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0 注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。 注意: 所有依赖的函数必须明确地在源文件中 #include ， 不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。
#include<iostream> #include<sstream> #include<cmath> #include<algorithm> #include<string> #include<vector> using namespace std; struct point{ //坐标位置点 int x; int y; }; int num=25;//步数不会比这个大 int m,n;//迷宫大小 char maze[100][100];//迷宫 int vis[100][100]={0};//标记是否走过 vector<point> step;// 步数 int flag=1; //标记是否有出口 int dir[4][2] = {{-1,0},{0,-1},{0,1},{1,0}}; void dfs(int x,int y) { if(maze[x][y]=='B') { flag=0; num=step.size()<num?step.size():num; return; } vector<point>::iterator it; it=step.end(); it--; char nc=maze[(*it).x][(*it).y]; for(int i=0;i<4;i++) { int nx = x + dir[i][0]; int ny = y + dir[i][1]; if(nx<m && nx>=0 && ny<n &&ny>=0 && maze[nx][ny]!=nc && maze[nx][ny]!='A' && vis[nx][ny] == 0) { point next; next.x=nx; next.y=ny; step.push_back(next); vis[nx][ny] =1; dfs(nx,ny); step.erase(step.end()-1); vis[nx][ny] = 0; } } if(flag) { num=0; } } int main(){ cin>>m; n=m; for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { cin>>maze[i][j]; } } point st; st.x=0; st.y=0; step.push_back(st); dfs(0,0); cout<<num-1<<endl; return 0; }路径之谜
小明冒充X星球的骑士，进入了一个奇怪的城堡。 城堡里边什么都没有，只有方形石头铺成的地面。
假设城堡地面是 n x n 个方格。【如图1.png】所示。
按习俗，骑士要从西北角走到东南角。 可以横向或纵向移动，但不能斜着走，也不能跳跃。 每走到一个新方格，就要向正北方和正西方各射一箭。 （城堡的西墙和北墙内各有 n 个靶子）
同一个方格只允许经过一次。但不必走完所有的方格。
如果只给出靶子上箭的数目，你能推断出骑士的行走路线吗？
有时是可以的，比如图1.png中的例子。
本题的要求就是已知箭靶数字，求骑士的行走路径（测试数据保证路径唯一）
输入： 第一行一个整数N(0<N<20)，表示地面有 N x N 个方格 第二行N个整数，空格分开，表示北边的箭靶上的数字（自西向东） 第三行N个整数，空格分开，表示西边的箭靶上的数字（自北向南）
输出： 一行若干个整数，表示骑士路径。
为了方便表示，我们约定每个小格子用一个数字代表，从西北角开始编号: 0,1,2,3… 比如，图1.png中的方块编号为：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
示例： 用户输入： 4 2 4 3 4 4 3 3 3
程序应该输出： 0 4 5 1 2 3 7 11 10 9 13 14 15
资源约定： 峰值内存消耗 < 256M CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0 注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。 注意: 所有依赖的函数必须明确地在源文件中 #include ， 不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。
#include<iostream> #include<sstream> #include<cmath> #include<algorithm> #include<string> #include<vector> using namespace std; struct point{ int x; int y; }; int m,n; //char maze[100][100]; int vis[100][100]={0}; vector<point> step; int flag=1; int dir[4][2] = {{-1,0},{0,-1},{0,1},{1,0}}; void dfs(int x,int y,int Nor[],int Wst[]) { for(int i=0;i<n;i++) { if(Nor[i]<0 || Wst[i]<0) { return; } } if(x==n-1 && y==n-1) { flag=0; int tag=1; for(int i=0;i<n;i++) { if(Nor[i]!=0 || Wst[i]!=0) { tag=0; return; } } if(tag) { //cout<<"get"<<endl; vector<point>::iterator it; for(it=step.begin();it!=step.end();it++) { int p=4*(*it).x+(*it).y; cout<<p<<" "; } return; } } for(int i=0;i<4;i++) { int nx = x + dir[i][0]; int ny = y + dir[i][1]; if(nx<m && nx>=0 && ny<n && ny>=0 && vis[nx][ny] == 0) { point next; next.x=nx; next.y=ny; step.push_back(next); vis[nx][ny] =1; Nor[ny]--; Wst[nx]--; dfs(nx,ny,Nor,Wst); step.erase(step.end()-1); vis[nx][ny] = 0; Nor[ny]++; Wst[nx]++; } } } int main(){ cin>>m; n=m; int Nth[n]; int Wst[n]; for(int i=0;i<m;i++) { cin>>Nth[i]; } for(int i=0;i<m;i++) { cin>>Wst[i]; } point st; st.x=0; st.y=0; vis[0][0]=1; Nth[0]--; Wst[0]--; step.push_back(st); dfs(0,0,Nth,Wst); return 0; }自己写的如有错误欢迎批评指正
