C - 亿夏网

C - 小明系列故事――捉迷藏

这个题目看了一下题解，感觉没有很难，应该是可以自己敲出来的，感觉自己好蠢。。。

这个是一个bfs 用bfs就很好写了，首先可以预处理出大明和二明能被发现的位置，标记一下。

然后跑bfs，注意这个bfs记录一下状态，记录一下是否看到了大明和二明。

这个题目和之前写的旅游这个题目很像，所以还是很好写的

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <iostream>
#include <string>
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
using namespace std;
const int maxn = 1e5 + 10;
typedef long long ll;
int n, m, t;
char s[110][110];
bool flaga[110][110], flagb[110][110];

void checka(int x,int y)
{
    int i = x, j = y;
    while (s[i][j] != 'X'&&i >= 1 && s[i][j] != 'E') flaga[i][j] = 1, i--;
    i = x;
    while (s[i][j] != 'X'&&i <= n && s[i][j] != 'E') flaga[i][j] = 1, i++;
    i = x;
    while (s[i][j] != 'X'&&j <= m && s[i][j] != 'E') flaga[i][j] = 1, j++;
    j = y;
    while (s[i][j] != 'X'&&j >= 1 && s[i][j] != 'E') flaga[i][j] = 1, j--;
}

void checkb(int x,int y)
{
    int i = x, j = y;
    while (s[i][j] != 'X'&&i >= 1 && s[i][j] != 'D') flagb[i][j] = 1, i--;
    i = x;
    while (s[i][j] != 'X'&&i <= n && s[i][j] != 'D') flagb[i][j] = 1, i++;
    i = x;
    while (s[i][j] != 'X'&&j <= m && s[i][j] != 'D') flagb[i][j] = 1, j++;
    j = y;
    while (s[i][j] != 'X'&&j >= 1 && s[i][j] != 'D') flagb[i][j] = 1, j--;
}

int dx[] = { 0,1,-1,0 };
int dy[] = { 1,0,0,-1 };

struct node
{
    int x, y, now;
    node(int x=0,int y=0,int now=0):x(x),y(y),now(now){}
};
int dp[110][110][5];
bool vis[110][110][5];
int bfs(int sx,int sy)
{
    int ans = inf;
    queue<node>que;
    int tmp = 0;
    memset(vis, 0, sizeof(vis));
    if (flaga[sx][sy]) tmp |= (1 << 0);
    if (flagb[sx][sy]) tmp |= (1 << 1);
    dp[sx][sy][tmp] = 0;
    que.push(node(sx, sy, tmp));
    while(!que.empty())
    {
        node u = que.front(); que.pop();
        int x = u.x, y = u.y, now = u.now;
        if (now == 3)ans = min(ans, dp[x][y][now]);
        for(int i=0;i<4;i++)
        {
            int tx = x + dx[i];
            int ty = y + dy[i];
            int tmp1 = now;
            if (tx<1 || ty<1 || tx>n || ty>m) continue;
            if (s[tx][ty] == 'X') continue;
            if (s[tx][ty] == 'E') continue;
            if (s[tx][ty] == 'D') continue;
            if (flaga[tx][ty]) tmp1 |= (1 << 0);
            if (flagb[tx][ty]) tmp1 |= (1 << 1);

            if (vis[tx][ty][tmp1]) continue;
            vis[tx][ty][tmp1] = 1;
            dp[tx][ty][tmp1] = dp[x][y][now] + 1;
            que.push(node(tx, ty, tmp1));
        }
    }
    return ans;
}

int main()
{
    int tim;
    scanf("%d", &tim);
    for(int cas=1;cas<=tim;cas++)
    {
        int sx = 0, sy = 0;
        scanf("%d%d%d", &n, &m, &t);
        memset(flaga, 0, sizeof(flaga));
        memset(flagb, 0, sizeof(flagb));
        for (int i = 1; i <= n; i++) {
            scanf("%s", s[i] + 1);
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s[i][j] == 'D') checka(i, j);
                if (s[i][j] == 'E') checkb(i, j);
                if (s[i][j] == 'S') sx = i, sy = j;
            }
        }
        int ans=bfs(sx, sy);
        printf("Case %d:
", cas);
        if (ans <= t) printf("%d
", ans);
        else printf("-1
");
    }
    return 0;
}

View Code

db爱好运动，但是单纯的运动会使得他很枯燥，现在他想边跑步边看风景。已知现在有n个风景点（编号为1号~n号），同时有m条道路将这n个风景点连接起来。

这些风景点总共有3类：A，B，C；为了方便表示，我们令 A=0，B=1，C=2。db一开始在1号风景点（可以为A，B，C类）。现在db想在跑步的过程中经过至少一个B类风景点的同时至少经过一个C类风景点，最后再回到1号风景点。现在db想要在尽可能短的时间内跑步结束，你能帮他找出一条路程最短同时满足题目条件的路径吗？

C

C - 小明系列故事――捉迷藏

相关推荐