魔鬼之城的感想

之城的感想"/>

魔鬼之城的感想

首先，大家先看一下题吧。 魔鬼之城
题有下列条件：

1. 可以向8个方向进行移动
2. 移动步数必须为房间内的魔法数字
3. 如果移动后超出了地图，则不能向该方向移动。
4. 不能连续朝两个方向移动。
5. 需要从（1,1）的位置移动到（n,m）的位置

条件就是这些了，下面是我的思路：
首先，是8个方向，一定不能错了。然后思路就和广搜一样了，不过需要注意一点，同一个点的每一个方向都是不一样的，所以要增加一个维度来表示每一个方向。
同样的思路适用于 棋盘

代码如下：

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <iomanip>
#include <math.h>
#include <cmath>
#include <ctime>
#include <cstdio>
#define inf 0x7fffffff
#define ll long long
//#include <windows.h>
//#include <bits/stdc++.h>
using namespace std;
/*
输入:输出:*/
int n,m;//n*m的矩阵
int map[110][110];//初始地图
struct node {int x,y;//坐标int way;//方向int step;//记录已经走了几步
} edge[100010];
int head=1;
int tail=1;
int flag;
int book[110][110][10];//标记是否走过
int nxtx[10]= {0,-1,1,0,0,-1,-1,1,1};
int nxty[10]= {0,0,0,-1,1,-1,1,1,-1}; //8个方向
void bfs() {edge[head].step=0;//初始化edge[head].x=1;edge[head].y=1;edge[head].way=9;
//	book[1][1]=1;tail++;while(head<tail) {for(int i=1; i<=8; i++) { //遍历8个方向if(edge[head].way!=i) { //如果不是一样的跳跃方向 int nx=edge[head].x+nxtx[i]*map[edge[head].x][edge[head].y];//临时的两个坐标int ny=edge[head].y+nxty[i]*map[edge[head].x][edge[head].y];if(nx>=1&&ny>=1&&nx<=n&&ny<=m&&book[nx][ny][i]==0) {//如果没有超出边界且没有遍历edge[tail].x=nx;edge[tail].y=ny;book[nx][ny][i]=1;edge[tail].step=edge[head].step+1;edge[tail].way=i;tail++;if(nx==n&&ny==m) {flag=1;break;}}}}if(flag)break;head++;}
}
int main() {
//freopen("***.in","r",stdin);
//freopen("***.out","w",stdout);scanf("%d%d",&m,&n);//先列后行 for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) {scanf("%d",&map[i][j]);}}
//cout <<endl;
//for(int i=1;i<=n;i++){
//	for(int j=1;j<=m;j++){
//		cout << map[i][j] <<" ";
//	}
//	cout << endl;
//}bfs();if(n==1&&m==1){flag=1;} if(flag) {cout << edge[tail-1].step << endl;} else {cout <<"NEVER" << endl;}return 0;
}