站点图标 陌路寒暄

共享单车

code

共享单车

时间： 1ms        内存：128M

描述：

共享单车走进烟台，小明决定尝试。小明启动共享单车app，轻松地找到附近的单车。那么问题来了，到最近的那辆单车，小明大约要走多少米呢？
现在简化问题。将地图设定成一个由100米*100米的像素块组成的二维平面区域。如果一个方块内有单车，则像素块显示为字符“x”；如果此方块内是可以通行的路，则显示为“.”；再如果方块是建筑物，则显示为“*”，建筑物不能通行。
小明在地图上的位置显示为“o”，可以朝，“上”、“下”、“左”，“右”，“左上”，“左下”，“右上”，“右下”八个方向走。下图所示为一个小明站在像素方块O，如果小明向右走到X，则走100米；如果向右上走，则走141米（不需要开方）。
假设小明和单车都在方块的中央。现在给出 T 幅根据以上规则建立的地图，地图行数和列数分别为 n 和 m，请分别估算小明要走多少米才能到最近的单车？

如果计算中出现小数，那么直接舍弃。最后的输出的结果为整型。
给出的地图中至少有一辆单车，如果最终无法到达单车的位置，输出-1。

输入：

第1行，T，表示下面有 T 组测试数据
对于每组测试数据
（1）第1行，n和m ,表示地图的大小；
（2）第2行开始，给出具体的地图 。

输出：

T行数据
每行1个整数，表示问题的解

示例输入：

2
3 8
.....x..
.o...x..
........
8 10
.***......
.***......
.***..x...
..........
.....*****
..o..*****
.......x..
...*******

示例输出：

400
523

提示：

参考答案（内存最优[1184]）：

#include <queue>
#include <cstdio>
#include <cstring>
char mp[105][105];
struct node
{
    int x,y,sum;
}S,c,t;
bool operator <(node a,node b){return a.sum>b.sum;}
std::priority_queue<node> q;
int dir[8][2]={{0,1},{1,0},{0,-1},{-1,0},{-1,1},{1,1},{1,-1},{-1,-1}};
void BFS()
{
    q.push(S);
    while(!q.empty())
    {
        c=q.top();
        if(mp[c.x][c.y]=='x')
        {
            printf("%d\n",c.sum+1);
            return;
        }
        for(int i=0;i<8;i++)
        {
            t.x=c.x+dir[i][0],t.y=c.y+dir[i][1];
            if(dir[i][0]&&dir[i][1])
                t.sum=c.sum+141;
            else
                t.sum=c.sum+100;
            if(mp[t.x][t.y]=='.')
            {
                q.push(t);
                mp[t.x][t.y]=0;
            }
            if(mp[t.x][t.y]=='x')
                t.sum-=1,q.push(t);
        }
        q.pop();
    }
    printf("-1\n");
}
int main()
{
    int T,n,m;
    scanf("%d",&T);
    while(T--)
    {
        memset(mp,0,sizeof(mp));
        while(!q.empty())
            q.pop();
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                scanf(" %c",&mp[i][j]);
                if(mp[i][j]=='o')
                    S.x=i,S.y=j,S.sum=0;
            }
        BFS();
    }
    return 0;
}

参考答案（时间最优[0]）：

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
#define MAXN		110
#define MAXM		110
#define CROSS		141
#define STRAIGHT	100
bool isw[MAXN][MAXM];
char a[MAXN][MAXM] = {0};
int dx[8] = {0,1,0,-1,1,-1,1,-1};
int dy[8] = {1,0,-1,0,1,1,-1,-1};
int Min;	//走过的最少步数
int n,m;	//行数和列数

struct Node{
int x;
int y;
int s;	//走到当前位置用了多少米
};

bool judge(int x,int y)
{
    if(x<0 || x>=n || y<0 || y>=m)
        return true;
    if(isw[x][y])
        return true;
    if(a[x][y]=='*')
        return true;
    return false;
}

void bfs(int cx,int cy)
{
    queue <Node> q;
    Node cur,next;
    cur.x = cx;
    cur.y = cy;
    cur.s = 0;
    isw[cur.x][cur.y] = true;
    q.push(cur);
    while(!q.empty()){
        cur = q.front();
        q.pop();
        if(a[cur.x][cur.y]=='x'){
			if(cur.s < Min)
				Min = cur.s;
		}
        int i,nx,ny;
        for(i=0;i<8;i++){
            nx = cur.x + dx[i];
            ny = cur.y + dy[i];
            if(judge(nx,ny))
                continue;
            //可以走
            //next = cur;
            next.x = nx;
            next.y = ny;
            next.s = cur.s + (dx[i]&&dy[i]?CROSS:STRAIGHT);
			isw[nx][ny] = true;
            q.push(next);
        }
    }
}

int main()
{
	int T;
	int i,j,cx,cy;
	scanf("%d",&T);
	while(T--){
		memset(isw,0,sizeof(isw));
		memset(a,0,sizeof(a));
		Min = 999999999;

		scanf("%d%d",&n,&m);
		getchar();
		for(i=0;i<n;i++){
			for(j=0;j<m;j++){
				scanf("%c",&a[i][j]);
				if(a[i][j]=='o')
					cx = i,cy = j;
			}
			getchar();
		}
		bfs(cx,cy);
		if(Min==999999999)
			printf("-1\n");
		else
			printf("%d\n",Min);
	}
	return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。

退出移动版