WY7. 地牢逃脱
描述
给定一个 n 行 m 列的地牢，其中 '.' 表示可以通行的位置，'X' 表示不可通行的障碍，牛牛从 (x0 , y0 ) 位置出发，遍历这个地牢，和一般的游戏所不同的是，他每一步只能按照一些指定的步长遍历地牢，要求每一步都不可以超过地牢的边界，也不能到达障碍上。地牢的出口可能在任意某个可以通行的位置上。牛牛想知道最坏情况下，他需要多少步才可以离开这个地牢。输入描述
每个输入包含 1 个测试用例。每个测试用例的第一行包含两个整数 n 和 m（1 <= n, m <= 50），表示地牢的长和宽。接下来的 n 行，每行 m 个字符，描述地牢，地牢将至少包含两个 '.'。接下来的一行，包含两个整数 x0, y0，表示牛牛的出发位置（0 <= x0 < n, 0 <= y0 < m，左上角的坐标为 （0, 0），出发位置一定是 '.'）。之后的一行包含一个整数 k（0 < k <= 50）表示牛牛合法的移动方式的数量，接下来的 k 行，每行两个整数 dx, dy 表示每次可选择移动的行和列步长（-50 <= dx, dy <= 50）输出描述
输出一行一个数字表示最坏情况下需要多少次移动可以离开地牢，如果永远无法离开，输出 -1。以下测试用例中，牛牛可以上下左右移动，在所有可通行的位置.上，地牢出口如果被设置在右下角，牛牛想离开需要移动的次数最多，为3次。示例1
输入:
3 3 ... ... ... 0 1 4 1 0 0 1 -1 0 0 -1
输出:
3
C 解法, 执行用时: 2ms, 内存消耗: 356KB, 提交时间: 2018-10-16
#include<stdio.h>
struct node {
int x;
int y;
int step;
};
int main() {
struct node que[2501];
int n, m, x0, y0, k, i, j, next[51][2], head, tail, book[51][51] = { 0 }, tx, ty,result;
char a[51][51];
scanf("%d %d", &n, &m);
for (i = 0; i < n; i++) {
scanf("%s", a[i]);
}
scanf("%d %d", &x0, &y0);
scanf("%d", &k);
for (i = 0; i < k; i++) {
scanf("%d %d", &next[i][0], &next[i][1]);
}
head = 1;
tail = 1;
que[tail].x = x0;
que[tail].y = y0;
que[tail].step = 0;
tail++;
book[x0][y0] = 1;
while (head < tail) {
for (i = 0; i < k; i++) {
tx = que[head].x + next[i][0];
ty = que[head].y + next[i][1];
if (tx<0||ty<0||tx >= n || ty >= m || a[tx][ty] == 'X') {
continue;
}
if (a[tx][ty] == '.'&&book[tx][ty] == 0) {
que[tail].x = tx;
que[tail].y = ty;
que[tail].step = que[head].step + 1;
tail++;
book[tx][ty] = 1;
}
}
head++;
}
result = que[tail-1].step;
for (i = 0; i < n; i++) {
for (j = 0; j < m; j++) {
if (book[i][j] == 0 && a[i][j] == '.') {
result = -1;
}
}
}
printf("%d", result);
}
C 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2020-09-23
#include <stdio.h>
struct node
{
int x;
int y;
int step;
};
int main()
{
struct node que[2501];
int n,m,x0,y0,k,i,j,next[51][2],head,tail,book[51][51] = {0},tx,ty,result;
char a[51][51];
scanf("%d %d", &n, &m);
for(i=0; i<n; i++)
{
scanf("%s",a[i]);
}
scanf("%d %d", &x0, &y0);
scanf("%d", &k);
for(i=0; i<k; i++)
{
scanf("%d %d", &next[i][0],&next[i][1]);
}
head = 1;
tail = 1;
que[tail].x = x0;
que[tail].y = y0;
que[tail].step = 0;
tail++;
book[x0][y0] = 1;
while(head < tail)
{
for(i=0; i<k; i++)
{
tx = que[head].x + next[i][0];
ty = que[head].y + next[i][1];
if(tx<0||ty<0||tx>=n||ty>=m||a[tx][ty]=='X')
{
continue;
}
if(a[tx][ty]=='.' && book[tx][ty] == 0)
{
que[tail].x = tx;
que[tail].y = ty;
que[tail].step = que[head].step+1;
tail++;
book[tx][ty] = 1;
}
}
head ++;
}
result = que[tail-1].step;
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(book[i][j] == 0 && a[i][j]=='.')
{
result = -1;
}
}
}
printf("%d", result);
}
C++ 解法, 执行用时: 2ms, 内存消耗: 408KB, 提交时间: 2021-10-16
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main()
{
int n, m;
while(cin >> n >> m)
{
char c1;
vector<vector<int>> matrix(n,vector<int>(m));
int sum = 0;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
cin >> c1;
if(c1 == '.')
{
matrix[i][j] = 0;
sum ++;
}
else
{
matrix[i][j] = 1;
}
}
}
//cout << " sum = " << sum << endl;
int x0, y0;
cin >> x0 >> y0;
int k;
cin >> k;
vector<vector<int>> dir(k,vector<int>(2));
for(int i = 0; i < k; i++)
{
int dx, dy;
cin >> dx >> dy;
dir[i] = {dx,dy};
}
queue<pair<int,int>> q;
queue<int> lvs;
q.push({x0,y0});
lvs.push(0);
int level = 0;
sum --;
matrix[x0][y0] = 1;
while(!q.empty())
{
auto [curr_x,curr_y] = q.front();
q.pop();
level = lvs.front();
lvs.pop();
for(int i = 0; i < k; i++)
{
int next_x, next_y;
next_x = curr_x + dir[i][0];
next_y = curr_y + dir[i][1];
if(next_x >= 0 && next_x < n && next_y>=0 && next_y < m && matrix[next_x][next_y] == 0)
{
q.push({next_x,next_y});
lvs.push(level+1);
matrix[next_x][next_y] = 1;
sum--;
}
}
}
//cout << "result sum " << sum << endl;
if(sum > 0) level = -1;
cout << level << endl;
}
}
C++ 解法, 执行用时: 2ms, 内存消耗: 420KB, 提交时间: 2021-09-13
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
using namespace std;
int main() {
int n, m;
cin>>n>>m;
vector<string> vm(n);
for(int i=0; i<n; i++){
cin>>vm[i];
}
int x0, y0;
cin>>x0>>y0;
int k;
cin>>k;
vector<pair<int, int> > vp(k);
for(int i=0;i<k;i++){
cin>>vp[i].first>>vp[i].second;
}
vector<vector<int> > vis(n, vector<int>(m));
queue<pair<int, int> > q;
q.push(pair<int, int>(x0, y0));
vis[x0][y0] = 1;
while(!q.empty()){
int tx= q.front().first, ty = q.front().second;
q.pop();
for(int i=0;i<k;i++){
int sx = tx+vp[i].first, sy = ty+vp[i].second;
if(sx>=0&&sx<n&&sy>=0&&sy<m&&vis[sx][sy]==0&&vm[sx][sy]=='.'){
vis[sx][sy] = vis[tx][ty] + 1;
q.push(pair<int, int>(sx, sy));
}
}
}
int maxStep=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(vm[i][j]=='.'){
if(vis[i][j]==0){
cout<<-1;
return 0;
}
maxStep = max(maxStep, vis[i][j]);
}
}
}
cout<<maxStep-1;
return 0;
}
C 解法, 执行用时: 2ms, 内存消耗: 480KB, 提交时间: 2019-02-20
#include<stdio.h>
struct node {
int x;
int y;
int step;
};
int main() {
struct node que[2501];
int n, m, x0, y0, k, i, j, next[51][2], head, tail, book[51][51] = { 0 }, tx, ty,result;
char a[51][51];
scanf("%d %d", &n, &m);
for (i = 0; i < n; i++) {
scanf("%s", a[i]);
}
scanf("%d %d", &x0, &y0);
scanf("%d", &k);
for (i = 0; i < k; i++) {
scanf("%d %d", &next[i][0], &next[i][1]);
}
head = 1;
tail = 1;
que[tail].x = x0;
que[tail].y = y0;
que[tail].step = 0;
tail++;
book[x0][y0] = 1;
while (head < tail) {
for (i = 0; i < k; i++) {
tx = que[head].x + next[i][0];
ty = que[head].y + next[i][1];
if (tx<0||ty<0||tx >= n || ty >= m || a[tx][ty] == 'X') {
continue;
}
if (a[tx][ty] == '.'&&book[tx][ty] == 0) {
que[tail].x = tx;
que[tail].y = ty;
que[tail].step = que[head].step + 1;
tail++;
book[tx][ty] = 1;
}
}
head++;
}
result = que[tail-1].step;
for (i = 0; i < n; i++) {
for (j = 0; j < m; j++) {
if (book[i][j] == 0 && a[i][j] == '.') {
result = -1;
}
}
}
printf("%d", result);
}