Question

c++习题求大神解答

设有一个n*m的棋盘(2≤n≤50，2≤m≤50)，。在棋盘上任一点有一个中国象棋马，马走的规则为： 1.马走日字 2.马只能向右走
问题：当n，m 输入之后，从最左下角走到最右上角，即从(1,1)走到(n,m)，所需的步数最少是多少。若不存在路径，则输出"no"
输入
6 5

输出
3
输入
4 4

输出
2

Answer 1

这道题用bfs做就行了，bfs是广度优先搜索，不清楚的话可以去学习一下，主要的思路就是把马可以走的下两步加入到一个队列中，直到有一步走到了(n, m)点，记录ans并return，此时的ans就是最少的步数。

代码：

#include <set>
#include <map>
#include <queue>
#include <cmath>
#include <vector>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
using namespace std;
const int MX = 50 + 5;
const int INF = 1e9 + 5;
int n, m, ans;
int vis[MX][MX];
int go[][2] = {1, 2, 2, 1};
struct node{
    int x, y, cnt;
}now, nxt;
void bfs(){
    queue<node> q;
    now.x = 1;
    now.y = 1;
    now.cnt = 0;
    vis[now.x][now.y] = 1;
    q.push(now);
    while(!q.empty()){
        now = q.front();
        q.pop();
        if(now.x == n && now.y == m){
            ans = now.cnt;
            return ;
        }
        for(int i = 0; i < 2; i++){
            nxt.x = now.x + go[i][0];
            nxt.y = now.y + go[i][1];
            nxt.cnt = now.cnt + 1;
            if(vis[nxt.x][nxt.y] || nxt.x > n || nxt.y > m) continue;
            q.push(nxt);
            vis[nxt.x][nxt.y] = 1;
        }
    }
}
int main(){
    scanf("%d%d", &n, &m);
    bfs();
    cout << ans << endl;
    return 0;
}

Answer 2

哈哈，后面也是你问的？