洛谷P1301 魔鬼之城

传送门啦

一道广度优先搜索的题目。

结构体含义：

struct node{

	int x,y,dir;//坐标，方向

	int step;//当前步数

};

方向的标号受上面定义的 $ dx[ ] , dy [ ] $ 数组 的影响

这个题要注意的就是初始化起点的问题。

起点可以向右、右下、下三个方向，所以三个方向我们都需要处理并入队。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

using namespace std;

int n,m,map[105][105];

int dx[8] = {-1,-1,0,1,1,1,0,-1};

int dy[8] = {0,1,1,1,0,-1,-1,-1};

bool vis[105][105][8];

struct node{

	int x,y,dir;

	int step;

};

queue<node> q;

int main(){

	scanf("%d%d",&n,&m);

	for(int i=1;i<=m;i++)

		for(int j=1;j<=n;j++)

			scanf("%d",&map[i][j]);

	if(map[1][1] + 1 <= n){

		node s1;

		s1.x = 1;  s1.y = map[1][1] + 1;

		s1.dir = 2;

		s1.step = 1;

		vis[1][map[1][1] + 1][2] = 1;

		q.push(s1);

	}

	if(map[1][1] + 1 <= m){

		node s2;

		s2.x = map[1][1] + 1; s2.y = 1;

		s2.dir = 4;

		s2.step = 1;

		vis[map[1][1] + 1][1][4] = 1;

		q.push(s2);

	}

	if(map[1][1] + 1 <= n && map[1][1] + 1 <= m){

		node s3;

		s3.x = map[1][1] + 1;  s3.y = map[1][1] + 1;

		s3.dir = 3;

		s3.step = 1;

		vis[map[1][1] + 1][map[1][1] + 1][3] = 1;

		q.push(s3);

	}

	for(int i=0;i<8;i++)

		vis[1][1][i] = 1;

	while(!q.empty()){

		node now = q.front();

		q.pop();

		int tx,ty;

		for(int i=0;i<8;i++){

			if(i == now.dir)  continue;

			tx = now.x + dx[i] * map[now.x][now.y];

			ty = now.y + dy[i] * map[now.x][now.y];

			if(tx >= 1 && tx <= m && ty >= 1 && ty <= n && !vis[tx][ty][i]){

				if(ty == n && tx == m){

					printf("%d",now.step + 1);

					return 0;

				}

				node tmp;

				tmp.x = tx;  tmp.y = ty;

				tmp.step = now.step + 1;

				tmp.dir = i;

				vis[tx][ty][i] = 1;

				q.push(tmp);

			}

		}

	}

	printf("NEVER");

	return 0;

}