[USACO10OCT]Lake Counting S

题面翻译

由于近期的降雨，雨水汇集在农民约翰的田地不同的地方。我们用一个 $N\times M(1\leq N\leq 100, 1\leq M\leq 100)$ 的网格图表示。每个网格中有水（W） 或是旱地（.）。一个网格与其周围的八个网格相连，而一组相连的网格视为一个水坑。约翰想弄清楚他的田地已经形成了多少水坑。给出约翰田地的示意图，确定当中有多少水坑。

输入第 $1$ 行：两个空格隔开的整数：$N$ 和 $M$。

第 $2$ 行到第 $N+1$ 行：每行 $M$ 个字符，每个字符是 W 或 .，它们表示网格图中的一排。字符之间没有空格。

输出一行，表示水坑的数量。

题目描述

Due to recent rains, water has pooled in various places in Farmer John’s field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water (‘W’) or dry land (‘.’). Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors. Given a diagram of Farmer John’s field, determine how many ponds he has.

输入格式

Line 1: Two space-separated integers: N and M * Lines 2..N+1: M characters per line representing one row of Farmer John’s field. Each character is either ‘W’ or ‘.’. The characters do not have spaces between them.

输出格式

Line 1: The number of ponds in Farmer John’s field.

样例 #1

样例输入 #1

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

样例输出 #1

3

提示

OUTPUT DETAILS: There are three ponds: one in the upper left, one in the lower left, and one along the right side.

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 110;

int n, m;
char g[N][N];
bool st[N][N]; //存状态：淹没淹过
int res = 0;

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

void dfs(int x, int y){
    for(int i = 0; i < 8; i++){
        int a = x + dx[i], b = y + dy[i];

        if(a < 0 || a >= n || b < 0 || b >= m) continue;
        if(g[a][b] != 'W') continue;
        if(st[a][b]) continue;

        st[a][b] = true;
        dfs(a, b);
    }
}

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++){
        scanf("%s", g[i]);
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j< m; j++){
            if(g[i][j] == 'W' && !st[i][j]){
                dfs(i, j);
                res++;
            } 
        }
    }
    printf("%d\n", res);
    return 0;
}

入门

题目描述

不是任何人都可以进入桃花岛的，黄药师最讨厌像郭靖一样呆头呆脑的人。所以，他在桃花岛的唯一入口处修了一条小路，这条小路全部用正方形瓷砖铺设而成。有的瓷砖可以踩，我们认为是安全的，而有的瓷砖一踩上去就会有喷出要命的毒气，那你就死翘翘了，我们认为是不安全的。你只能从一块安全的瓷砖上走到与他相邻的四块瓷砖中的任何一个上，但它也必须是安全的才行。

由于你是黄蓉的朋友，她事先告诉你哪些砖是安全的、哪些砖是不安全的，并且她会指引你飞到第一块砖上（第一块砖可能在任意安全位置），现在她告诉你进入桃花岛的秘密就是：如果你能走过最多的瓷砖并且没有死，那么桃花岛的大门就会自动打开了，你就可以从当前位置直接飞进大门了。

注意：瓷砖可以重复走过，但不能重复计数。

输入格式

第一行两个正整数 $W$ 和 $H$，分别表示小路的宽度和长度。

以下 $H$ 行为一个 $H\times W$ 的字符矩阵。每一个字符代表一块瓷砖。其中，. 代表安全的砖，# 代表不安全的砖，@ 代表第一块砖。

输出格式

输出一行，只包括一个数，即你从第一块砖开始所能安全走过的最多的砖块个数（包括第一块砖）。

样例 #1

样例输入 #1

11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........

样例输出 #1

59

提示

数据规模与约定

对于全部的测试点，保证 $1 \leq W,H\le 20$。

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 30;

int n, m;  //n行m列
char g[N][N];
int res = 0;  //记录走过的瓷砖数
bool st[N][N];  //记录每块瓷砖 走过或者没走过

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

//当前访问到的坐标（x， y）
void dfs(int x, int y){
    for(int i = 0; i < 4; i++){
        int a = x + dx[i], b = y + dy[i];

        if(a < 0 || a >= n || b < 0 || b >= m) continue;
        if(g[a][b] != '.') continue;
        if(st[a][b]) continue;

        //走（a， b）这个点
        st[a][b] = true;
        res++;
        dfs(a, b);
    }
}

int main()
{
    scanf("%d %d", &m, &n);
    for(int i = 0; i < n; i++){
        scanf("%s", g[i]);
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(g[i][j] == '@'){
                st[i][j] = true;
                dfs(i, j);
            }
        }
    }
    res++;
    printf("%d\n", res);
    return 0;
}

八数码难题

题目描述

在 $3\times 3$ 的棋盘上，摆有八个棋子，每个棋子上标有 $1$ 至 $8$ 的某一数字。棋盘中留有一个空格，空格用 $0$ 来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为 $123804765$），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

输入格式

输入初始状态，一行九个数字，空格用 $0$ 表示。

输出格式

只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数。保证测试数据中无特殊无法到达目标状态数据。

样例 #1

样例输入 #1

283104765

样例输出 #1

4

提示

样例解释

图中标有 $0$ 的是空格。绿色格子是空格所在位置，橙色格子是下一步可以移动到空格的位置。如图所示，用四步可以达到目标状态。

并且可以证明，不存在更优的策略。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<unordered_map>
#include <queue>
#include<string>

using namespace std;

const int N = 10;

string s;
queue<string> q;
unordered_map<string, int> dist;
unordered_map<string, int> vis;  //哈希表来存每个状态的标记--> 1 或 2
string end1 = "123804765";

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

int bfs(string s)
{
    dist[end1] = 0;
    q.push(s), q.front();
    vis[s] = 1, vis[end1] = 2;

    while(q.size()){
        auto t = q.front();
        q.pop();

        int distance  = dist[t];  //记录队头到起点的距离
        int flag = vis[t];  //存队头的标记

        int x = t.find('0');  //找到‘0’ 的位置
        int xx = x / 3, xy = x % 3;  //一维——> 二维

        //只有二维坐标才可以去遍历四个方向
        for(int i = 0; i < 4; i++){
            int a = xx + dx[i], b = xy + dy[i];

            if(a < 0 || a >= 3 || b < 0 || b >= 3) continue;

            int tmp = a * 3 + b;  //二维坐标再转换回一位坐标
            swap(t[x], t[tmp]);

            //此时的t是下一个状态的t：队头拓展出来的点的状态
            if(vis[t] + flag == 3){  //如果队头的标记 和 对头拓展出来的点的标记 相加 为3，（1+2），就说明两个标记重合，到此，搜索结束
                int res1 = dist[t];  //存拓展出来的点 距离起点的位置
                swap(t[x], t[tmp]);  //再交换回来，此时的t就是取出的队头了！
                int res2 = dist[t];  //再用res2 存一下队头的距离
                return res1 + res2 + 1;
            }

            if(!dist.count(t)){
                dist[t] = distance + 1;
                vis[t] = flag;  //拓展出来的点 的 标记 要 跟随 队头的标记
                q.push(t);
            }

            swap(t[x], t[tmp]);  //恢复现场
        }
    }
    return -1;
}

int main()
{
    cin >> s;  //start
    if(s == end1){
        printf("0\n");
        return 0;
    }
    int res = bfs(s);
    //printf("%d\n", res);
    cout << res << endl;
    return 0;
}

离开中山路

题目背景

《爱与愁的故事第三弹·shopping》最终章。

题目描述

爱与愁大神买完东西后，打算坐车离开中山路。现在爱与愁大神在 $x_1,y_1$ 处，车站在 $x_2,y_2$ 处。现在给出一个 $n \times n(n \le 1000)$ 的地图，$0$ 表示马路，$1$ 表示店铺（不能从店铺穿过），爱与愁大神只能垂直或水平着在马路上行进。爱与愁大神为了节省时间，他要求最短到达目的地距离（每两个相邻坐标间距离为 $1$）。你能帮他解决吗？

输入格式

第 $1$ 行包含一个数 $n$。

第 $2$ 行到第 $n+1$ 行：整个地图描述（$0$ 表示马路，$1$ 表示店铺，注意两个数之间没有空格）。

第 $n+2$ 行：四个数 $x_1,y_1,x_2,y_2$。

输出格式

只有 $1$ 行，即最短到达目的地距离。

样例 #1

样例输入 #1

3
001
101
100
1 1 3 3

样例输出 #1

4

提示

对于 $20\%$ 数据，满足 $1\leq n \le 100$。

对于 $100\%$ 数据，满足 $1\leq n \le 1000$。

#include<iostream>
#include<algorithm>
#include<cstring>

#define x first
#define y second

using namespace std;
typedef pair<int, int> PII;

const int N = 1100;

int n;
char g[N][N];
int dist[N][N];
int vis[N][N];
PII q[N * N];
int x1, y1, x2, y2;

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

int bfs()
{
    memset(dist, -1, sizeof dist);
    memset(vis, -1, sizeof vis);

    dist[x1][y1] = 0, dist[x2][y2] = 0;
    vis[x1][y1] = 1, vis[x2][y2] = 2;
    q[0] = {x1, y1}, q[1] = {x2, y2};
    int hh = 0, tt = 1;

    while(hh <= tt){
        auto t = q[hh++];

        for(int i = 0; i < 4; i++){
            int a = t.x + dx[i], b = t.y + dy[i];

            if(a < 1 || a > n || b < 1 || b > n) continue;
            if(g[a][b] != '0') continue;

            if(vis[a][b] + vis[t.x][t.y] == 3){
                return dist[t.x][t.y] + dist[a][b] + 1;
            }
            if(dist[a][b] >= 0) continue;

            dist[a][b] = dist[t.x][t.y] + 1;
            if(vis[a][b] == -1) vis[a][b] = vis[t.x][t.y];

            q[++tt] = {a, b};
        }
    }
    return -1;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", g[i] + 1);
    }

    scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
    int res = bfs();
    printf("%d\n", res);
    return 0;
}
//不知道为什么AC不了

八数码难题

题目描述

在 $3\times 3$ 的棋盘上，摆有八个棋子，每个棋子上标有 $1$ 至 $8$ 的某一数字。棋盘中留有一个空格，空格用 $0$ 来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为 $123804765$），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

输入格式

输入初始状态，一行九个数字，空格用 $0$ 表示。

输出格式

只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数。保证测试数据中无特殊无法到达目标状态数据。

样例 #1

样例输入 #1

283104765

样例输出 #1

4

提示

样例解释

图中标有 $0$ 的是空格。绿色格子是空格所在位置，橙色格子是下一步可以移动到空格的位置。如图所示，用四步可以达到目标状态。

并且可以证明，不存在更优的策略。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include <queue>
#include<unordered_map>


using namespace std;

string end0 = "123804765";
unordered_map<string, int> dist;  //dist记录走到string这个状态需要走多少步
queue<string> q;

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

int bfs(string start)
{
    dist[start] = 0;
    q.push(start);

    while(q.size()){
        auto t = q.front();
        q.pop();

        if(t == end0){
            return dist[t];
        }

        int distance = dist[t];

        int a = t.find('0'); //找到字符0的位置（即下标）
        int x1 = a / 3, y1 = a % 3;  //一维数组下标转换为二维数组下标（将字符串3*3矩阵--把字符0在3*3中的坐标算出来

        for(int i = 0; i < 4; i++){
            int x2 = x1 + dx[i], y2 = y1 + dy[i];

            if(x2 < 0 || x2 >= 3 || y2 < 0 || y2 >= 3) continue;

            int tmp = x2 * 3 + y2;  //将3*3矩阵坐标转换为一位字符串的坐标
            swap(t[a], t[tmp]);  //在字符串中将这两个位置互换

            //如果下个位置没被访问过的话--进入循环
            if(!dist.count(t)){  //count函数（map里的函数）-->例如：count(1)-->看map里有没有key值为1的元素，如果有则返回1，否则返回0；
                dist[t] = distance + 1;
                q.push(t);
            }

            swap(t[a], t[tmp]);  //恢复现场，给下个方向做准备
        }
    }
    return -1;
}

int main()
{
    string start;
    cin >> start;

    int res = bfs(start);
    printf("%d\n", res);
    return 0;
}

//哈希表--map 或 unoredered_map

小明的游戏

题目描述

小明最近喜欢玩一个游戏。给定一个$n \times m$的棋盘，上面有两种格子#和@。游戏的规则很简单：给定一个起始位置和一个目标位置，小明每一步能向上，下，左，右四个方向移动一格。如果移动到同一类型的格子，则费用是$0$，否则费用是$1$。请编程计算从起始位置移动到目标位置的最小花费。

输入格式

输入文件有多组数据。
输入第一行包含两个整数$n$，$m$，分别表示棋盘的行数和列数。
输入接下来的$n$行，每一行有$m$个格子（使用#或者@表示）。
输入接下来一行有四个整数$x_1, y_1, x_2, y_2$，分别为起始位置和目标位置。
当输入$n$，$m$均为$0$时，表示输入结束。

输出格式

对于每组数据，输出从起始位置到目标位置的最小花费。每一组数据独占一行。

样例 #1

样例输入 #1

2 2
@#
#@
0 0 1 1
2 2
@@
@#
0 1 1 0
0 0

样例输出 #1

2
0

提示

对于20%的数据满足：$1 \le n, m \le 10$。
对于40%的数据满足：$1 \le n, m \le 300$。
对于100%的数据满足：$1 \le n, m \le 500$。

//《deque》 队列的头既有进队列的也有出队列的，队列的尾既有进队列的也有出队列的--即双端
#include<iostream>
#include<algorithm>
#include<cstring>
#include<deque>

#define fi first
#define sc second

using namespace std;

const int N = 510;
typedef pair<int, int> PII;

int n, m;
char g[N][N];
int x1, x2, y1, y2;
deque<PII> q;
int dist[N][N];

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

int bfs(int x, int y){
    q.push_back({x, y});
    dist[x][y] = 0;

    while(q.size()){
        auto t = q.front();
        q.pop_front();
        //printf("t = (%d %d)\n", t.fi, t.sc);
        char ch = g[t.fi][t.sc];

        for(int i = 0; i < 4; i++){
            int a = t.fi + dx[i], b = t.sc + dy[i];

            if(a < 0 || a >= n || b < 0 || b >= m) continue;
            if(dist[a][b] >=  ch) continue;

            if(g[a][b] == ch){
                dist[a][b] = dist[t.fi][t.sc];
                q.push_front({a, b});
            }

            if(g[a][b] != ch){
                dist[a][b] = dist[t.fi][t.sc] + 1;
                q.push_back({a, b});
            }

            if(a == x2 && b == y2) return dist[x2][y2];
        }
    }
    return -1;
}

int main()
{
    while(cin >> n >> m, n || m){
        for(int i = 0; i < n; i++){
            scanf("%s", g[i]);
        }
        memset(dist, -1, sizeof dist);
        q.clear();
        cin >> x1 >> y1 >> x2 >> y2;
        int res = bfs(x1, y1);
        cout << res << endl;
    }
    return 0;
}

//《deque》 队列的头既有进队列的也有出队列的，队列的尾既有进队列的也有出队列的--即双端

给定三个整数数组

A=[A1,A2,…AN]
,
B=[B1,B2,…BN]
,
C=[C1,C2,…CN]
,

请你统计有多少个三元组 (i,j,k)
满足：

1≤i,j,k≤N
Ai<Bj<Ck
输入格式
第一行包含一个整数 N
。

第二行包含 N
个整数 A1,A2,…AN
。

第三行包含 N
个整数 B1,B2,…BN
。

第四行包含 N
个整数 C1,C2,…CN
。

输出格式
一个整数表示答案。

数据范围
1≤N≤105
,
0≤Ai,Bi,Ci≤105
输入样例：
3
1 1 1
2 2 2
3 3 3
输出样例：
27

//二分（之前提交的）
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 100010;

int n;
int a[N], b[N], c[N];

//在A中找到最后一个小于B的数的位置
//在C中找到第一个大于B的数的位置
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for(int i = 1; i <= n; i++) scanf("%d", &b[i]);
    for(int i = 1; i <= n; i++) scanf("%d", &c[i]);

    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + n);
    sort(c + 1, c + 1 + n);

    long long res = 0;  //long long --最坏情况下要用long long
    for(int i = 1, IndexA = 1, IndexC = 1; i <= n; i++){  //IndexA--指针 IndexC同理
        int B = b[i];
        while(IndexA <= n && a[IndexA] < B){  //在A中找到最后一个小于B的数的位置
            IndexA++;
        }
        while(IndexC <= n && c[IndexC] <= B){  //在C中找到第一个大于B的数的位置
            IndexC++;
        }
        res += (long long)(IndexA - 1) * (n - IndexC + 1);   //强转成long long
    }
    printf("%lld\n", res);
    return 0;
}

A-B 数对

题目背景

出题是一件痛苦的事情！

相同的题目看多了也会有审美疲劳，于是我舍弃了大家所熟悉的 A+B Problem，改用 A-B 了哈哈！

题目描述

给出一串正整数数列以及一个正整数 $C$，要求计算出所有满足 $A - B = C$ 的数对的个数（不同位置的数字一样的数对算不同的数对）。

输入格式

输入共两行。

第一行，两个正整数 $N,C$。

第二行，$N$ 个正整数，作为要求处理的那串数。

输出格式

一行，表示该串正整数中包含的满足 $A - B = C$ 的数对的个数。

样例 #1

样例输入 #1

4 1
1 1 2 3

样例输出 #1

3

提示

对于 $75\%$ 的数据，$1 \leq N \leq 2000$。

对于 $100\%$ 的数据，$1 \leq N \leq 2 \times 10^5$，$0 \leq a_i <2^{30}$,$1 \leq C < 2^{30}$。

2017/4/29 新添数据两组

//b指针中又分了两个指针—-b1和b2
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 200010;

int n, C;
int q[N];

int main()
{
    scanf("%d %d", &n, &C);
    for(int i = 1; i <= n; i++){
        scanf("%d", &q[i]);
    }

    sort(q + 1, q + 1 + n);

    long long res = 0;
    for(int a = 1, b1 = 1, b2 = 1; a <= n; a++){
        while(b1 <= a && q[a] - q[b1] >= C){
            b1++;
        }
        while(b2 <= a && q[a] - q[b2] > C){
            b2++;
        }
        res += b1 - b2;
    }

    printf("%lld\n", res);
    return 0;
}

一、题目描述
给定两个升序排序的有序数组 A AA 和 B BB，以及一个目标值 x xx。

数组下标从 0 00 开始。

请你求出满足 A [ i ] + B [ j ] = x A[i]+B[j]=xA[i]+B[j]=x 的数对 ( i , j ) (i,j)(i,j)。

数据保证有唯一解。

输入格式
第一行包含三个整数 n , m , x n,m,xn,m,x，分别表示 A 的长度，B 的长度以及目标值 x。

第二行包含 n nn 个整数，表示数组 A。

第三行包含 m mm 个整数，表示数组 B。

输出格式
共一行，包含两个整数 i ii 和 j jj。

数据范围
数组长度不超过 1 0 5 10^510
5
。
同一数组内元素各不相同。
1 ≤ 1≤1≤ 数组元素 ≤ 1 0 9 ≤10^9≤10
9

输入样例：

4 5 6
1 2 4 7
3 4 6 8 9
1
2
3
输出样例：

1 1
————————————————

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 100010;

int n, m, x;
int a[N], b[N];

int main()
{
    scanf("%d %d %d", &n, &m, &x);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }
    for(int i = 1; i <= n; i++){
        scanf("%d", &b[i]);
    }

    for(int i = 1, j = m; i <= n; i++){
        while(j >= 1 && a[i] + b[j] > x){
            j--;
        }
        if(a[i] + b[j] == x){
            printf("%d %d\n", i - 1, j - 1);
            return 0;
        }
    }
    return 0;
}

输入一个 n
行 m
列的整数矩阵，再输入 q
个询问，每个询问包含四个整数 x1,y1,x2,y2
，表示一个子矩阵的左上角坐标和右下角坐标。

对于每个询问输出子矩阵中所有数的和。

输入格式
第一行包含三个整数 n，m，q
。

接下来 n
行，每行包含 m
个整数，表示整数矩阵。

接下来 q
行，每行包含四个整数 x1,y1,x2,y2
，表示一组询问。

输出格式
共 q
行，每行输出一个询问的结果。

数据范围
1≤n,m≤1000
,
1≤q≤200000
,
1≤x1≤x2≤n
,
1≤y1≤y2≤m
,
−1000≤矩阵内元素的值≤1000
输入样例：
3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4
输出样例：
17
27
21

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m, k;
int q[N][N];
int s[N][N];  //前缀和数组的和

int main()
{
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
             scanf("%d", &q[i][j]);
        s[i][j] = q[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }
    }
    while(k--){
        int x1, x2, y1, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        printf("%d\n", s[x2][y2] - s[x2][y1 -1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]);
        //**printf("%d\n", s[x2][y2] - s[x2][y1 -1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]);**
    }
    return 0;
}