链接:https://ac.nowcoder.com/acm/contest/338/B
来源:牛客网
The first line has two positive integers n, m , separated by spaces(1 <= n, m <= 100), n for the row, m for the column
Next there are two positive integers x, y, separated by spaces(1 <= x <= n, 1 <= y <= m) indicating the coordinates of the teaching building
Next is a map of n rows and m columns, 0 indicate a open space and 1 indicate a obstacles.
For each test case, output a single line containing an integer giving the minimum time little bearBaby takes to reach the teaching building, in minutes.
First grid in the upper left corner is(1,1)
bfs板子题
#include <iostream> #include <stdio.h> #include <queue> #include<cstring> using namespace std; typedef pair<int, int> P; #define max_n 102 #define max_m 102 #define inf 1000000 int N,M; int map[max_n][max_m]; int direct[max_n][max_m]; int sx,sy; int ans; int dx[4]= {1,0,-1,0},dy[4]= {0,1,0,-1}; int bfs(int sx,int sy,int gx,int gy) { int nx,ny; queue<P> Q; memset(direct, inf, sizeof(direct)); Q.push(P(sx,sy)); direct[sx][sy]=0; while (Q.size()) { P q=Q.front(); Q.pop(); if (q.first==gx&&q.second==gy) break; else { for (int i=0; i<=3; i++) { nx=q.first+dx[i]; ny=q.second+dy[i]; if (nx<0||nx>N||ny<0||ny>M||map[nx][ny]==1||direct[nx][ny]<inf) continue; else { direct[nx][ny]=direct[q.first][q.second]+1; Q.push(P(nx,ny)); } } } } return direct[gx][gy]; } int main() { int gx,gy; scanf("%d %d",&N,&M); scanf("%d %d",&gx,&gy); for (int i=0; i<N; i++) for(int j = 0; j<M; j++) { scanf("%d",&map[i][j]); } ans=bfs(0, 0, gx-1, gy-1); printf("%d\n",ans); return 0; }
原文:https://www.cnblogs.com/DWVictor/p/10229975.html