HJ156 走迷宫

题目题解(95)讨论(34)排行简单 通过率33.65% 时间限制3秒 空间限制256M知识点广度优先搜索(BFS)校招时部分企业笔试将禁止编程题跳出页面为提前适应练习时请使用在线自测而非本地IDE。描述给定一个 n×mn×m 的网格。你从起点 (xs,ys)(xs​,ys​) 出发每一次可以向上、下、左、右移动一步若不超出边界。某些格子上存在障碍物无法经过。求从 (xs,ys)(xs​,ys​) 移动到终点 (xt,yt)(xt​,yt​) 的最少步数若无法到达输出 −1−1。输入描述在一行上输入两个整数 n,m(1≦n,m≦1000)n,m(1≦n,m≦1000)代表网格的行数与列数。在一行上输入四个整数 xs,ys,xt,yt(1≦xs,xt≦n; 1≦ys,yt≦m)xs​,ys​,xt​,yt​(1≦xs​,xt​≦n; 1≦ys​,yt​≦m)代表起点与终点的坐标。此后 nn 行第 ii 行输入一个长度为 mm 的字符串 gigi​其中∙ ∙若 gi,j*gi,j​*表示第 ii 行第 jj 列为障碍物∙ ∙若 gi,j.gi,j​.表示该格子可通行。保证起点所在格子可通行。输出描述输出一个整数表示最少移动次数若无法到达输出 −1−1。示例1输入5 5 1 1 5 5 ..... ****. ..... **.** .....复制输出12复制示例2输入5 5 1 1 4 5 ..... ****. ..... **.** .....复制输出-1复制示例3输入5 5 1 1 5 5 ..... ****. ..... ***** .....复制输出-1#includeiostream #includevector #includequeue #define INF 1e7 using namespace std; typedef struct node { int row; int col; node(int f, int t) :row(f), col(t) {} }Node; typedef struct direct { int crow; int ccol; direct(int f, int t) :crow(f), ccol (t) {} }Direct; vectorchar vec[1001]; int dp[1001][1001]; Direct dir[4] { Direct {1,0},Direct{-1,0},Direct{0,1},Direct{0,-1} }; int main() { char c; int xs, ys, n, m, xt, yt; queueNode qu; cin n m; cin xs ys xt yt; for (int i 0; i n; i) { for (int j 0; j m; j) dp[i][j] -1; } for (int i 1; i n; i) { for (int j 1; j m; j) { cin c; if (vec[i].empty()) vec[i].push_back(0); vec[i].push_back(c); } } qu.push(Node{ xs,ys }); while (!qu.empty()) { Node point qu.front(); qu.pop(); for (int i 0; i 4; i) { int row point.row dir[i].crow; int col point.col dir[i].ccol; if (row 1 row n col 1 col m vec[row][col] . dp[row][col] -1) { qu.push(Node{ row,col }); dp[row][col] dp[point.row][point.col] 1; } } } if (dp[xt][yt] ! -1) cout ((xt xs yt ys ) ? 0 : dp[xt][yt] 1); else cout -1; }