题目描述

Farmer John has taken the cows to a vacation out on the ocean! The cows are living on N (1 <= N <= 15) islands, which are located on an R x C grid (1 <= R, C <= 50). An island is a maximal connected group of squares on the grid that are marked as 'X', where two 'X's are connected if they share a side. (Thus, two 'X's sharing a corner are not necessarily connected.)

Bessie, however, is arriving late, so she is coming in with FJ by helicopter. Thus, she can first land on any of the islands she chooses. She wants to visit all the cows at least once, so she will travel between islands until she has visited all N of the islands at least once.

FJ's helicopter doesn't have much fuel left, so he doesn't want to use it until the cows decide to go home. Fortunately, some of the squares in the grid are shallow water, which is denoted by 'S'. Bessie can swim through these squares in the four cardinal directions (north, east, south, west) in order to travel between the islands. She can also travel (in the four cardinal directions) between an island and shallow water, and vice versa.

Find the minimum distance Bessie will have to swim in order to visit all of the islands. (The distance Bessie will have to swim is the number of distinct times she is on a square marked 'S'.) After looking at a map of the area, Bessie knows this will be possible.

给你一张r*c的地图，有’S’,’X’,’.’三种地形，所有判定相邻与行走都是四连通的。我们设’X’为陆地，一个’X’连通块为一个岛屿，’S’为浅水，’.’为深水。刚开始你可以降落在任一一块陆地上，在陆地上可以行走，在浅水里可以游泳。并且陆地和浅水之间可以相互通行。但无论如何都不能走到深水。你现在要求通过行走和游泳使得你把所有的岛屿都经过一边。Q：你最少要经过几个浅水区？保证有解。

输入输出格式

输入格式：

* Line 1: Two space-separated integers: R and C.

* Lines 2..R+1: Line i+1 contains C characters giving row i of the
grid. Deep water squares are marked as '.', island squares are marked as
'X', and shallow water squares are marked as 'S'.

输出格式：

* Line 1: A single integer representing the minimum distance Bessie has to swim to visit all islands.

输入输出样例

输入样例#1：

5 4

XX.S

.S..

SXSS

S.SX

..SX
输出样例#1：

3

说明

There are three islands with shallow water paths connecting some of them.

Bessie can travel from the island in the top left to the one in the middle, swimming 1 unit, and then travel from the middle island to the one in the bottom right, swimming 2 units, for a total of 3 units.

注意到岛屿数量只有15个，所以考虑状压。

于是我们先跑dfs，把所有岛屿找出来，然后对于每个岛屿跑spfa求出经过的浅滩数。

然后设f[i][j]表示在i岛，经过岛屿的状态为j的最少经过的浅滩。

然后就是普通的DP。

话说把三个不难的知识块放在一起考仍然增加不了它的难度。

一开始是不想写spfa，直接暴力求出任意两个坐标的距离，因为复杂度在允许范围之内，写起来又方便...

于是TLE三个点，不得不说数据一点都不弱(-_-||

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

using namespace std;

inline int read(){

    int res=;char ch=getchar();

    while(!isdigit(ch))ch=getchar();

    while(isdigit(ch)){res=(res<<)+(res<<)+(ch^);ch=getchar();}

    return res;

}

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

int n, m;

char mp[][];

bool vis[][];

int belong[][], tot;

int f[][<<], bin[];

void dfs(int x, int y)

{

    belong[x][y] = tot;

    for (int i =  ; i <=  ; i ++)

    {

        int tx = x + dx[i], ty = y + dy[i];

        if (tx <=  or tx > n or ty <=  or ty > m) continue;

        if (mp[tx][ty] != 'X') continue;

        if (belong[tx][ty]) continue;

        dfs(tx, ty);

    }

}

int dis[][], w[][][][];

struct date{

    int x, y, stp;

};

inline void bfs(int X, int Y)

{

    memset(vis, , sizeof vis);

    queue <date> q;

    q.push((date){X, Y, });

    vis[X][Y] = ;

    w[X][Y][X][Y] = ;

    while(!q.empty())

    {

        int x = q.front().x, y = q.front().y, tp = q.front().stp;

        q.pop();

        vis[x][y] = ;

        w[X][Y][x][y] = min(w[X][Y][x][y], tp);

        for (int i =  ; i <=  ; i ++)

        {

            int tx = x + dx[i], ty = y + dy[i];

            if (tx <=  or tx > n or ty <=  or ty > m) continue;

            if (vis[tx][ty]) continue;

            if (mp[tx][ty] == '.') continue;

            q.push((date){tx, ty, tp + (mp[tx][ty]=='S')});

        }

    }

}

int main()

{

    n = read(), m = read();

    for (int i =  ; i <= n ; i ++)

        for (int j =  ; j <= m ; j ++)

            cin >> mp[i][j];

    for (int i =  ; i <= n ; i ++)

    {

        for (int j =  ; j <= m ; j ++)

        {

            if (!belong[i][j] and mp[i][j] == 'X')

            {

                tot++;

                dfs(i, j);

            }

        }

    }

    memset(w, 0x3f, sizeof w);

    for (int i =  ; i <= n ; i ++)

    {

        for (int j =  ; j <= m ; j ++)

        {

            bfs(i, j);

        }

    }

    memset(dis, 0x3f, sizeof dis);

    for (int i =  ; i <= n ; i ++)

        for (int j =  ; j <= m ; j ++)

            for (int x =  ; x <= n ; x ++)

                for (int y =  ; y <= m ; y ++)

                    dis[belong[i][j]][belong[x][y]] = min(dis[belong[i][j]][belong[x][y]], w[i][j][x][y]);

    memset(f, 0x3f, sizeof f);

    bin[] = ;for(int i=;i<=;i++) bin[i]=bin[i-]<<;

    for (int i =  ; i <= tot ; i ++) f[i][bin[i]] = ;

    for (int j =  ; j <= (<<tot)- ; j ++)

    {

        for (int i =  ; i <= tot ; i ++)

        {

            if ((j & bin[i]) == ) continue;

            for (int k =  ; k <= tot ; k ++)

            {

                if (k == i) continue;

                if (j & bin[k]) continue;

                f[k][j+bin[k]] = min(f[k][j+bin[k]], f[i][j] + dis[i][k]);

            }

        }

    }

    int ans = 1e9;

    for (int i =  ; i <= tot ; i ++)

        ans = min(ans, f[i][(<<tot)-]);

    printf("%d\n", ans);

    return ;

}

复杂度允许的暴力

然后无奈只好写spfa...

于是调了好久好久...

最后发现好像个给每个联通快记大小的时候，少了初始点。

然后加上了91分，实在不想改了一个特判走人。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

using namespace std;

inline int read(){

    int res=;char ch=getchar();

    while(!isdigit(ch))ch=getchar();

    while(isdigit(ch)){res=(res<<)+(res<<)+(ch^);ch=getchar();}

    return res;

}

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

int n, m;

char mp[][];

bool vis[][];

int belong[][], tot;

int f[][<<], bin[];

int siz[];

struct date{

    int x, y;

}block[][];

void dfs(int x, int y)

{

    belong[x][y] = tot;

    for (register int i =  ; i <=  ; i ++)

    {

        int tx = x + dx[i], ty = y + dy[i];

        if (tx <=  or tx > n or ty <=  or ty > m) continue;

        if (mp[tx][ty] != 'X') continue;

        if (belong[tx][ty]) continue;

        block[tot][++siz[tot]] = (date){tx, ty};

        dfs(tx, ty);

    }

}

int dis[][], w[][];

inline void bfs(int bl)

{

    memset(vis, , sizeof vis);

    memset(w, 0x3f, sizeof w);

    queue <date> q;

    for (register int i =  ; i <= siz[bl] ; i ++)

    {

        q.push(block[bl][i]);

        w[block[bl][i].x][block[bl][i].y] = ;

        vis[block[bl][i].x][block[bl][i].y] = ;

    }

    while(!q.empty())

    {

        int x = q.front().x, y = q.front().y;

        q.pop();

        vis[x][y] = ;

        for (register int i =  ; i <=  ; i ++)

        {

            int tx = x + dx[i], ty = y + dy[i];

            if (tx <=  or tx > n or ty <=  or ty > m) continue;

            if (mp[tx][ty] == '.') continue;

            if (mp[tx][ty] == 'X')

            {

                if (w[tx][ty] > w[x][y])

                {

                    w[tx][ty] = w[x][y];

                    if (!vis[tx][ty]) vis[tx][ty] = , q.push((date){tx, ty});

                }

                dis[bl][belong[tx][ty]] = min(dis[bl][belong[tx][ty]], w[tx][ty]);

                dis[belong[tx][ty]][bl] = min(dis[belong[tx][ty]][bl], w[tx][ty]);

            }

            else

            {

                if (w[tx][ty] > w[x][y] + )

                {

                    w[tx][ty] = w[x][y] + ;

                    if (!vis[tx][ty]) vis[tx][ty] = , q.push((date){tx, ty});

                }

            }

        }

    }

}

int main()

{

    n = read(), m = read();

    for (register int i =  ; i <= n ; i ++)

        for (register int j =  ; j <= m ; j ++)

            cin >> mp[i][j];

    for (register int i =  ; i <= n ; i ++)

    {

        for (register int j =  ; j <= m ; j ++)

        {

            if (!belong[i][j] and mp[i][j] == 'X')

            {

                tot++;

                block[tot][++siz[tot]] = (date){i, j} ;

                dfs(i, j);

            }

        }

    }

    memset(dis, 0x3f, sizeof dis);

    for (register int i =  ; i <= tot ; i ++)

    {

        dis[i][i] = ;

        bfs(i);

    }

    memset(f, 0x3f, sizeof f);

    for (register int i =  ; i <= tot ; i ++) f[i][<<(i-)] = ;

    for (register int j =  ; j <= (<<tot)- ; j ++)

    {

        for (register int i =  ; i <= tot ; i ++)

        {

            if ((j & (<<(i-))) == ) continue;

            for (register int k =  ; k <= tot ; k ++)

            {

                if (k == i) continue;

                if (j & (<<(k-))) continue;

                f[k][j|(<<(k-))] = min(f[k][j|(<<(k-))], f[i][j] + dis[i][k]);

            }

        }

    }

    int ans = 1e9;

    for (register int i =  ; i <= tot ; i ++)

        ans = min(ans, f[i][(<<tot)-]);

    if (ans == ) ans = ;

    printf("%d\n", ans);

    return ;

}

$\sum_{age=16}^{18} hardworking = success$

最新文章

  1. C语言正则表达式详解 regcomp() regexec() regfree()详解
  2. Java的super调用案例: super.getClass()返回的是子类自己
  3. 精通Web Analytics 2.0 （1） 引言
  4. POJ 3740
  5. Spring事务管理者与Spring事务注解--声明式事务
  6. 第9章 使用ssh服务管理远程主机。
  7. python中新式类和经典类的区别
  8. QTP检查点和参数化_百度一下
  9. JS 利用数组拼接html字符串
  10. 将[{},{}]转为dict
  11. 【转】《我的WCF之旅》博文系列汇总
  12. 警惕！MySQL成数据勒索新目标
  13. PHP预定义变量$_SERVER
  14. 提取http接口响应报文中需要的值，获得的是string，使用dict转换为字典处理
  15. Android SVN上传项目
  16. 继承ActionSupper类报错 --Struts2
  17. Android代码安全工具集
  18. 使用Zabbix服务端本地邮箱账号发送报警邮件及指定报警邮件操作记录
  19. Linux 磁盘管理命令
  20. Spark学习之路 （十九）SparkSQL的自定义函数UDF

热门文章

  1. 小白专场-是否同一颗二叉搜索树-python语言实现
  2. 创建型模式总结(2.x)
  3. query 与 params 使用
  4. Java匹马行天下之 Java国出了个Java——举国欢庆
  5. jenkins自动化部署项目8 -- 新建job（服务代码部署在linux上）
  6. Mysql INSTR函数
  7. 【ADO.NET基础-GridView】GridView的编辑、更新、取消、删除以及相关基础操作代码
  8. 自学React 入门
  9. .Net Core 商城微服务项目系列（一）：使用IdentityServer4构建基础登录验证
  10. chown、chgrp、chmod