挑战程序设计竞赛-day3

Property Distribution

题意：
在H * W的矩形果园里有苹果、梨、蜜柑三种果树， 相邻（上下左右）的同种果树属于同一个区域，给出果园的果树分布，求总共有多少个区域。

输入：
多组数据，每组数据第一行为两个整数H，W（H <= 100, W <= 100）， H =0 且 W = 0代表输入结束。以下H行W列表示果园的果树分布， 苹果是@，梨是#， 蜜柑是*。
输出：
对于每组数据，输出其区域的个数。

#include <cstdio>
#include <cstdlib>
#include <queue>
#include <cstring>
using namespace std;
const int N = 110;
char matrix[N][N];
bool isTrue[N][N];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

void change(int H, int W, int sx, int sy, char ch) {
    queue<pair<int, int> > que;
    que.push(pair<int, int>(sx, sy));
    while(que.size()) {
        int nx = que.front().first;
        int ny = que.front().second;
        que.pop();
        for(int i = 0; i < 4; i++) {
            int x = nx + dx[i];
            int y = ny + dy[i];
            if(0 <= x && x < H && 0 <= y && y <= W && isTrue[x][y] == false && matrix[x][y] == ch) {
                isTrue[x][y] = true;
                matrix[x][y] = '.';
                que.push(pair<int, int>(x, y));
            }
        }
    } 
}

int solve(int H, int W) {
    int count = 0;
    for(int i = 0; i < H; i++) {
        for(int j = 0; j < W; j++) {
            if(matrix[i][j] != '.') {
                change(H, W, i, j, matrix[i][j]);
                count++;
            } 
        }
    }
    return count;
}

int main() {
    int row = 1, col = 1;
    while(scanf("%d%d", &row, &col) && row !=0 && col != 0) {
        memset(isTrue, 0, sizeof(isTrue));
        for(int i = 0; i < row; i++) {
            scanf("%s", matrix[i]);
        }
        printf("%d\n", solve(row, col));
    }
}

Cheese

在H * W的地图上有N个奶酪工厂，分别生产硬度为1-N的奶酪。有一只吃货老鼠准备从老鼠洞出发吃遍每一个工厂的奶酪。老鼠有一个体力值，初始时为1，每吃一个工厂的奶酪体力值增加1（每个工厂只能吃一次），且老鼠只能吃硬度不大于当前体力值的奶酪。

老鼠从当前格走到相邻的无障碍物的格（上下左右）需要时间1单位，有障碍物的格不能走。走到工厂上时即可吃到该工厂的奶酪，吃奶酪时间不计。问吃遍所有奶酪最少用时。

输入：第一行三个整数H(1 <= H <= 1000)、W(1 <= W <=1000)、N(1 <= N <= 9)，之后H行W列为地图， “.“为空地， ”X“为障碍物，”S“为老鼠洞， 1-N代表硬度为1-N的奶酪的工厂。

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int N = 1010;
char M[N][N];
bool mark[N][N];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int sx, sy;
int total = 1;

void clear(queue<pair<int, int> > &q) {
    queue<pair<int, int> > empty;
    swap(empty, q);
}

void solve(int row, int col, int n) {
    memset(mark, 0, sizeof(mark));
    queue<pair<int, int> > que;
    que.push(pair<int, int>(sx, sy));
    int count = 1;
    while(que.size()) {
        int size = que.size();
        for(int k = 0; k < size; k++) {
            int nx = que.front().first;
            int ny = que.front().second;
            que.pop();
            for(int i = 0;i < 4; i++) {
                int x = nx + dx[i];
                int y = ny + dy[i];
                if(0 <= x && x < row && 0 <= y && y < col && M[x][y] != 'X' && !mark[x][y]) {
                    que.push(pair<int, int>(x, y));
                    mark[x][y] = true;
                    if(M[x][y] != '.' && M[x][y] - '0' == count) {
                        memset(mark, 0, sizeof(mark));
                        M[x][y] = '.';
                        count += 1;
                        if(count > n) {
                            printf("%d\n", total);
                            return ;
                        }
                        k = size;
                        clear(que);
                        que.push(pair<int, int>(x, y));
                        break;
                    }
                }
            }    
        }
        total += 1;
    }
    
}

int main() {
    int row, col, n;
    scanf("%d%d%d", &row, &col, &n);
    for(int i = 0; i < row; i++) {
        scanf("%s", M[i]);
        for(int j = 0; j < col; j++) {
            if(M[i][j] == 'S') {
                sx = i;
                sy = j;
            }
        }
    }
    solve(row, col, n);
}

Meteor Shower

Bessie从原点出发，然后有N个流星会在某个时刻落下，它们会破坏砸到的这个方格还会破坏

四边相邻的方块，输出多少时间之后他可以到达安全的地方。如果可能，输出最优解，不可能则输出-1。

分析：这道题目通过广搜算法来解决，但是还是需要判重，不然会TLE。还有一个要注意的是，他可能一开始就被炸到。
原文链接：https://blog.csdn.net/vizard_/article/details/77141820

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int N = 310;
int Map[N][N];
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int mark[N][N];
// 检测是否到达安全的地方，即它所在的位置四周都没有炸弹，或者说是已经被炸掉了的地方

struct node {
    int x;
    int y;
    int step;
}temp, a;

bool operator < (const node &a, const node &b) {
    return a.step > b.step;
}

void bfs() {
    int i;
    memset(mark, 0, sizeof(mark));
    priority_queue<node> q;
    a.x = 0;
    a.y = 0;
    a.step = 0;
    q.push(a);
    mark[0][0] = 1;
    while(!q.empty()) {
        a = q.top();
        q.pop();
        if(Map[a.x][a.y] == -1) {
            printf("%d\n", a.step);
            return ;
        }
        for(int i = 0;i < 4; i++) {
            temp.x = a.x + dir[i][0];
            temp.y = a.y + dir[i][1];
            temp.step = a.step + 1;
            if(temp.x >= 0 && temp.y >= 0 && (Map[temp.x][temp.y] == -1 || Map[temp.x][temp.y] > temp.step)) {
                if(!mark[temp.x][temp.y]) {
                    q.push(temp);
                    mark[temp.x][temp.y] = 1;
                }
            }
        }
    }
    printf("-1\n");
}

int main() {
    int n, x, y, time, i, j;
    while(scanf("%d", &n) != EOF) {
        memset(Map, -1, sizeof(Map));
        for(int i = 0;i < n; i++) {
            scanf("%d%d%d", &x, &y, &time);
            if(Map[x][y] == -1) {
                Map[x][y] = time;
            } else {
                Map[x][y] = min(Map[x][y], time);
            }
            for(int j = 0; j < 4; j++) {
                int nx = x + dir[j][0];
                int ny = y + dir[j][1];
                if(nx >= 0 && ny >= 0) {
                    if(Map[nx][ny] == -1) {
                        Map[nx][ny] = time;
                    } else {
                        Map[nx][ny] = min(Map[nx][ny], time);
                    }
                }
            }
        }
        bfs();
    }
}