洛谷P1301 魔鬼之城

之城"/>

洛谷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;
}

转载于:.html