题目描述1

地上有一个 m 行和 n 列的方格，横纵坐标范围分别是 0∼m−1 和 0∼n−1。

一个机器人从坐标 (0,0) 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格。

但是不能进入行坐标和列坐标的数位之和大于 k 的格子。

请问该机器人能够达到多少个格子？

样例

原题

算法1

考虑情况

考虑数据：

k=0的情况考虑到----（输入值为0的情况经常见。）
0
5
6
答案：1

第二次wa：k不等于0，col和row为0--即房间为0 （极端情况）
所以以后bfs这样的要特判。
5
0
0
答案：1

其他:

1. 边界判断judge一定要写上，否则就会永无止境。
2. 开局要把我们第一个点的房间设为1.ans=1；否则他们之后会回来一次。
3. 根据题目2：终点是字符时要注意添加判断。

参考文献

无

C++ 代码

#include <iostream>
#include <string>
#include <queue>
#include <cstdlib>
#include <cstring>
using namespace std;

int row, col, k, ans;
int room[60][60];
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
struct node
{
    int x, y;
};

int judge(int a, int b)
{
    if (a >= 0 && b >= 0 && a < row && b < col)
        return 1;
    return 0;
}

int judge1(int n)
{
    int sum = 0;
    while (n)
    {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

void dfs()
{
    queue<node> q;
    node start, next;
    start.x = 0;
    start.y = 0;
    ans = 1;
    q.push(start);
    while (!q.empty())
    {
        start = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            next.x = start.x + dir[i][0];
            next.y = start.y + dir[i][1];
            if (judge(next.x, next.y) && room[next.x][next.y] == 0 && judge1(next.x) + judge1(next.y) <= k)
            {
                room[next.x][next.y] = 1;
                ans++;
                q.push(next);
            }
        }
    }
}

int main()
{

    while (t--)
    {
        cin >> k >> row >> col;
        ans = 0;
        room[0][0] = 1;
        dfs();
        cout << ans << endl;
        memset(room, 0, sizeof(room));
    }

    return 0;
}

题目描述2 武士风度的牛

农民 John 有很多牛，他想交易其中一头被 Don 称为 The Knight 的牛。

这头牛有一个独一无二的超能力，在农场里像 Knight 一样地跳（就是我们熟悉的象棋中马的走法）。

虽然这头神奇的牛不能跳到树上和石头上，但是它可以在牧场上随意跳，我们把牧场用一个 x，y 的坐标图来表示。

这头神奇的牛像其它牛一样喜欢吃草，给你一张地图，上面标注了 The Knight 的开始位置，树、灌木、石头以及其它障碍的位置，除此之外还有一捆草。

现在你的任务是，确定 The Knight 要想吃到草，至少需要跳多少次。

The Knight 的位置用 K 来标记，障碍的位置用 * 来标记，草的位置用 H 来标记。

样例

原题

算法1

收录原因：

if (judge(next.x, next.y) && (room[next.x][next.y] == '.'||room[next.x][next.y]=='H'))
【room[next.x][next.y]=='H'】
因为终点位置是H不是. 所以如果只是判断. 那我永远到不了终点。（昨天卡了我好久，我说为什么一直到不了终点。）

参考文献

无

C++ 代码

#include <iostream>
#include <string>
#include <queue>
#include <cstdlib>
#include <cstring>
using namespace std;

int row, col, k, ans;
char room[200][200];
int dir[8][2] = {{2, 1}, {-2, 1}, {2, -1}, {-2, -1}, {-1, 2}, {1, 2}, {-1, -2}, {1, -2}};
//int dir[8][2] = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2},{1, 2}, {2, -1}, {2, 1}};
int sx, sy, ex, ey;
struct node
{
    int x, y, step = 0;
};

int judge(int a, int b)
{
    if (a >= 1 && b >= 1 && a <= row && b <= col)
        return 1;
    return 0;
}

void dfs()
{
    queue<node> q;
    node start, next;
    start.x = sx;
    start.y = sy;
    start.step = 0;
    q.push(start);
    while (!q.empty())
    {
        start = q.front();
        q.pop();
        if (start.x == ex && start.y == ey)
        {
            ans = start.step;
            return;
        }
        for (int i = 0; i < 8; i++)
        {
            next.x = start.x + dir[i][0];
            next.y = start.y + dir[i][1];

            if (judge(next.x, next.y) && (room[next.x][next.y] == '.'||room[next.x][next.y]=='H'))
            {
                next.step = start.step + 1;
                room[next.x][next.y] = '*';
                q.push(next);
            }
        }
    }
}

int main()
{

    while (cin >> row >> col)
    {
        int x, y;
        for (y = col; y > 0; y--)
        {
            for (x = 1; x <= row; x++)
            {
                cin >> room[x][y];
                if (room[x][y] == 'K')
                {
                    sx = x;
                    sy = y;
                }
                if (room[x][y] == 'H')
                {
                    ex = x;
                    ey = y;
                }
            }
        }
        ans = 0;
        room[sx][sy] = '*';
        dfs();
        cout << ans << endl;
        memset(room, 0, sizeof(room));
    }

    return 0;
}
/*



                for (x =1 ; x < row; x++)
        {
            for (y = 1; y < col; y++)
            {
                cin >> room[x][y];
                if (room[x][y] == 'K')
                {
                    sx = x;
                    sy = y;
                }
                if (room[x][y] == 'H')
                {
                    ex = x;
                    ey = y;
                }
            }
        }
*/