怎么添加网站 多少钱,泉州市住房和乡村建设网站,北京网页设计公司兴田德润实惠,网站建设计入什么费用Description
一个迷宫由R行C列#xff08;1R#xff0c;C 40)格子组成#xff0c;有的格子里有障碍物#xff0c;不能走#xff0c;用‘#’表示#xff0c;#xff1b;有的格子是空地#xff0c;可以走#xff0c;用‘.’表示。迷宫左上角和右下角都是.。 给…Description
一个迷宫由R行C列1RC 40)格子组成有的格子里有障碍物不能走用‘#’表示有的格子是空地可以走用‘.’表示。迷宫左上角和右下角都是.。 给定一个迷宫求从左上角走到右下角最少需要走多少步。只能在水平方向或垂直方向走不能斜着走。注意计算步数要包括起点和终点。
Input
第一行输入迷宫的行数R以及列数C
后面R行每行C个字符字符由 . 或 # 组成
Output
一个整数表示步数若不能走到终点则输出“-1”。
Sample Input 1
4 4
..##
#...
#.#.
#.#.Sample Output 1
7
AC:
#includeiostream
#includealgorithm
#includecstring
using namespace std;
int64_t r,c,q[3000][5];
bool v[50][50],f;
char a[50][50];
int dx[4]{0,0,1,-1};
int dy[4]{1,-1,0,0};
void bfs(){int front0;int tail1;while(fronttail){front;for(int i0;i4;i){int xxq[front][1]dx[i];int yyq[front][2]dy[i];if(a[xx][yy].xxryycxx0yy0v[xx][yy]0){v[xx][yy]1;tail;q[tail][1]xx;q[tail][2]yy;q[tail][3]q[front][3]1;if(xxryyc){coutq[tail][3];f1;return;}}}}
}int main(){cinrc;for(int i1;ir;i){for(int j1;jc;j){cina[i][j];}}q[1][1]1;q[1][2]1;q[1][3]1;v[1][1]1;bfs();if(f0){cout-1;}return 0;
}
