您现在的位置是:首页 > 学习之路 > ACM||算法ACM||算法

POJ-3414 Pots

卞振伟2019-07-25【ACM||算法】人已围观

简介POJ-3414 Pots
BFS
两个水杯容量为 A, B, 目标容量C,水杯有填满、倒光、互倒操作,输出使两水杯之一达到目标容量的最快方式的路径
坑:
1.代码量长,十分容易写错代码,难以检查出来,特殊情况容易漏掉,(1,1,1) -> (FILL(1))
2.map<自定义结构体> 需要重载 <
3.BFS输出路径时使用string比较方便,用cin、cout不要用scanf,printf

#include <stdio.h>
#include <string.h>
#include <queue>
#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 20;
const int dir[4][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}};

struct Point {
    int x, y;
    Point() {}
    Point(int a, int b) { x = a; y = b; }
};
int m, n, d[N][N], tmp;
char g[N][N];

void init() {
    memset(g, 0, sizeof(g));
    tmp = 0;

    scanf("%d%d%*c", &m, &n);

    for (int i = 0; i < m; i++) {
        gets(g[i]);
        for (int j = 0; j < n; j++)
            if (g[i][j] == '#')
                tmp++;
    }
}

int bfs(int x1, int y1, int x2, int y2) {
    memset(d, INF, sizeof(d));

    d[x1][y1] = d[x2][y2] = 0;

    Point k, c;
    
    queue<Point> q;
    q.push(Point(x1, y1));
    q.push(Point(x2, y2));

    while ( !q.empty() ) {
        k = q.front(); q.pop();

        for (int i = 0; i < 4; i++) {
            c.x = k.x + dir[i][0]; c.y = k.y + dir[i][1];
            if (c.x < 0 || c.x >= m || c.y < 0 || c.y >= n) continue;
            if (g[c.x][c.y] != '#') continue;

            if (d[c.x][c.y] > d[k.x][k.y] + 1) {
                d[c.x][c.y] = d[k.x][k.y] + 1;
                q.push(c);
            }
        }
    }

    int ans = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) if (g[i][j] == '#') {
            ans = max(ans, d[i][j]);
        }
    }
    return ans;
}


int solve() {
    if (tmp <= 2) return 0;
    int ans = INF;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) if (g[i][j] == '#') {
            for (int k = 0; k < m; k++) {
                for (int t = 0; t < n; t++) {
                    if (k == i && t <= j) continue;
                    if (g[k][t] == '#')
                        ans = min(ans, bfs(i, j, k, t));
                }
            }
        }
    }
    return ans == INF ? -1 : ans;
}

int main () {
    int cas;
    scanf("%d", &cas);
    for (int i = 1; i <= cas; i++) {
        init();
        printf("Case %d: %d\n", i, solve());
    }
    return 0;
}

Tags:ACM   编程   个人   题解   算法   C|C++

很赞哦! ()

上一篇:POJ-3087 Shuffle'm Up

下一篇:FZU-2150 Fire Game

文章评论

站点信息

  • 建站时间:2018-11-25
  • 网站程序:帝国CMS7.5
  • 文章统计:118篇文章
  • 标签管理标签云
  • 统计数据百度统计
  • 网站地图XML网站地图
  • 微信公众号:扫描二维码,关注我的公众号
  • GitHub:扫描二维码,关注我的GitHub

客服在线

QQ客服

客服微信扫码

服务时间

周一至周日 9:00-21:00