《算法竞赛·快冲300题》每日一题:“超级骑士”

这篇具有很好参考价值的文章主要介绍了《算法竞赛·快冲300题》每日一题:“超级骑士”。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

算法竞赛·快冲300题》将于2024年出版,是《算法竞赛》的辅助练习册。
所有题目放在自建的OJ New Online Judge。
用C/C++、Java、Python三种语言给出代码,以中低档题为主,适合入门、进阶。


超级骑士” ,链接: http://oj.ecustacm.cn/problem.php?id=1810

题目描述

【题目描述】 现在在一个无限大的平面上,给你一个超级骑士。
   超级骑士有N种走法,请问这个超级骑士能否到达平面上的所有点。
   每种走法输入两个数字xx和yy,表示超级骑士可以从任意一点(x,y)走到(x+xx,y+yy)。
【输入格式】 输入第一行为正整数T,表示存在T组测试数据。(1≤T≤100)
   对于每组测试数据,第一行输入正整数N,表示有N种走法。(1≤N≤100)
   接下来N行,每行两个正整数xx和yy。(-100≤xx,yy≤100)。
【输出格式】 对于每组测试数据,如果可以到达平面上所有点,输出Yes,否则输出No。。
【输入样例】

2
3
1 0
0 1
-2 -1
5
3 4
-3 -6
2 -2
5 6
-1 4

【输出样例】

Yes
No

题解

  虽然题目问能不能到达所有的点,但其实不用真的检查是否能到所有的点。只要检查平面上的某个特定点,如果从它出发能到达它的上、下、左、右4个点,那么推广到任意一个点,它的上、下、左、右都能到达,整个平面就是可达的。
  题目给定-100≤xx, yy≤100,若定中心点(x, y)为(100, 100),那么走一步最远可到(0, 0)、(0, 200)、(200, 0)、(200, 200),检查以这4个点确定的区间内所有点。最后看是否能到达(x, y)的上、下、左、右4个点。
  本题是一个简单的遍历问题,用BFS或DFS都行,计算复杂度就是区间内点的数量,共200*200 = 40000个点,用BFS和DFS遍历一次即可。不过,DFS有栈空间的限制,本题的DFS需要用到很大的栈。为了保险,用BFS更好。
【重点】 注意DFS用到的栈大小。

C++代码

  下面是DFS代码,虽然简单,也有小技巧。从中心点(X, Y)出发开始遍历区间内的点,在任意时刻只要发现(X, Y)的上、下、左、右都已到达,可立即返回“Yes”,不用再遍历其他的点,这是剪枝的应用,代码第8行做这个判断。写DFS代码时,一定要注意是否能剪枝。

#include<bits/stdc++.h>
using namespace std;
int n, xx[110], yy[110];
int X=100, Y=100;                   //中心点(X,Y),从它出发
bool vis[210][210];
bool dfs(int x, int y){             //从(x,y)出发,把可以到达的点全部打上标记
    vis[x][y] = true;               //把当前点标记为已达
    if(vis[X-1][Y] && vis[X+1][Y] && vis[X][Y-1] && vis[X][Y+1]) return true; //有剪枝的作用
    for(int i = 1; i <= n; i++) {   //遍历n个方向
        int nx = x + xx[i];         //新坐标(nx, ny)
        int ny = y + yy[i];
        if(nx < 1 || nx > 200 || ny < 1 || ny > 200)  continue;  //判断越界
        if(vis[nx][ny])  continue;        //已经走过,不用再走
        if(dfs(nx, ny))  return true;
    }
    return false;
}
int main(){
    int T;    cin >> T;
    while(T--)    {
        cin >> n;
        for(int i = 1; i <= n; i++)     cin >> xx[i] >> yy[i];
        memset(vis, 0, sizeof(vis));
        if(dfs(X, Y))   cout<<"Yes"<<endl;
        else            cout<<"No"<<endl;
    }
    return 0;
}

BFS代码:

#include<bits/stdc++.h>
using namespace std;
int n,xx[110], yy[110];
int X=100,Y=100;                  //中心点(X,Y),从它出发
bool vis[210][210];
bool bfs(int x,int y){             //从(x,y)出发,把可以到达的点全部打上标记
    vis[x][y] = true;              //把当前点标记为已达
    queue<pair<int,int>>q;
    q.push({x,y});
    while(q.size())    {
        auto t = q.front();
        q.pop();
        if(vis[X-1][Y] && vis[X+1][Y] && vis[X][Y-1] && vis[X][Y+1])  return true;
        for(int i=1;i<=n;i++)  {     //遍历n个方向
            int nx = t.first+xx[i], ny = t.second+yy[i];
            if(nx < 1 || nx > 200 || ny < 1 || ny > 200)  continue;  //判断越界
            if(vis[nx][ny])  continue;    //已经走过,不用再走
            vis[nx][ny] = true;
            q.push({nx,ny});
        }
    }
    return false;
}
int main(){
    int T; cin>>T;
    while(T--){
        cin>>n;
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++)      cin>>xx[i]>>yy[i];
        if(bfs(X,Y)) cout<<"Yes\n";
        else         cout<<"No\n";

    }
    return 0;
}

Java代码

DFS代码,但是出错了,栈溢出,需要扩栈。

import java.util.Scanner;
public class Main {
    static int n;
    static int[] xx = new int[110];
    static int[] yy = new int[110];
    static int X = 100, Y = 100; // 中心点(X,Y),从它出发
    static boolean[][] vis = new boolean[210][210];

    public static boolean dfs(int x, int y) {
        vis[x][y] = true; // 把当前点标记为已达
        if (vis[X - 1][Y] && vis[X + 1][Y] && vis[X][Y - 1] && vis[X][Y + 1])
            return true; // 有剪枝的作用
        for (int i = 1; i <= n; i++) { // 遍历n个方向
            int nx = x + xx[i]; // 新坐标(nx, ny)
            int ny = y + yy[i];
            if (nx < 1 || nx > 200 || ny < 1 || ny > 200)     continue; // 判断越界
            if (vis[nx][ny])  continue; // 已经走过,不用再走
            if (dfs(nx, ny))  return true;
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        while (T-- > 0) {
            n = scanner.nextInt();
            for (int i = 1; i <= n; i++) {
                xx[i] = scanner.nextInt();
                yy[i] = scanner.nextInt();
            }
            for (int i = 0; i < 210; i++)
                for (int j = 0; j < 210; j++)
                    vis[i][j] = false;

            if (dfs(X, Y))   System.out.println("Yes");
            else              System.out.println("No");
        }
    }
}

BFS代码:不用担心DFS的栈空间问题。所以为了保险,还是用BFS更好。

import java.util.*;
public class Main {
    static int n, X = 100, Y = 100;
    static int[] xx = new int[110], yy = new int[110];
    static boolean[][] vis = new boolean[210][210];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            n = sc.nextInt();
            for (int i = 0; i < 210; i++)
                for (int j = 0; j < 210; j++)
                    vis[i][j] = false;
            for (int i = 1; i <= n; i++) {
                xx[i] = sc.nextInt();
                yy[i] = sc.nextInt();
            }
            if (bfs(X, Y))    System.out.println("Yes");
             else             System.out.println("No");            
        }
        sc.close();
    }
    static boolean bfs(int x, int y) {
        vis[x][y] = true;
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{x, y});
        while (!q.isEmpty()) {
            int[] t = q.poll();
            if (vis[X - 1][Y] && vis[X + 1][Y] && vis[X][Y - 1] && vis[X][Y + 1])  return true;
            for (int i = 1; i <= n; i++) {
                int nx = t[0] + xx[i], ny = t[1] + yy[i];
                if (nx < 1 || nx > 200 || ny < 1 || ny > 200)     continue;              
                if (vis[nx][ny])               continue; 
                vis[nx][ny] = true;
                q.offer(new int[]{nx, ny});
            }
        }
        return false;
    }
}

Python代码

DFS代码,注意要用setrecursionlimit扩栈。

import sys
sys.setrecursionlimit(1000000)
n = 0
xx,yy = [0] * 110, [0] * 110
X,Y = 100,100  # 中心点(X,Y),从它出发
vis = [[False] * 210 for _ in range(210)]
def dfs(x, y):  # 从(x,y)出发,把可以到达的点全部打上标记
    global vis
    vis[x][y] = True  # 把当前点标记为已达
    if vis[X-1][Y] and vis[X+1][Y] and vis[X][Y-1] and vis[X][Y+1]: return True  #有剪枝的作用
    for i in range(1, n + 1):      # 遍历n个方向
        nx = x + xx[i]             # 新坐标(nx, ny)
        ny = y + yy[i]
        if nx < 1 or nx > 200 or ny < 1 or ny > 200:      continue  # 判断越界
        if vis[nx][ny]:            continue  # 已经走过,不用再走
        if dfs(nx, ny):            return True
    return False
T = int(input())
while T > 0:
    T -= 1
    n = int(input())
    for i in range(1, n + 1):   xx[i], yy[i] = map(int, input().split())
    vis = [[False] * 210 for _ in range(210)]
    if dfs(X, Y):  print("Yes")
    else:        print("No")

BFS代码:文章来源地址https://www.toymoban.com/news/detail-580109.html

from queue import Queue
n, X, Y = 0, 100, 100
xx, yy = [0]*110, [0]*110
vis = [[False]*210 for _ in range(210)] 
def bfs(x, y):
    vis[x][y] = True
    q = Queue()
    q.put((x, y))
    while not q.empty():
        t = q.get()
        if vis[X-1][Y] and vis[X+1][Y] and vis[X][Y-1] and vis[X][Y+1]:  return True
        for i in range(1, n+1):
            nx, ny = t[0]+xx[i], t[1]+yy[i]
            if nx < 1 or nx > 200 or ny < 1 or ny > 200 or vis[nx][ny]:  continue
            vis[nx][ny] = True
            q.put((nx, ny))
    return False 
T = int(input())
while T:
    T -= 1
    n = int(input())
    for i in range(1, n + 1):   xx[i], yy[i] = map(int, input().split())
    vis = [[False]*210 for _ in range(210)]
    if bfs(X, Y):    print('Yes')
    else:            print('No')

到了这里,关于《算法竞赛·快冲300题》每日一题:“超级骑士”的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 《算法竞赛·快冲300题》每日一题:“松鼠与栗子”

    《 算法竞赛·快冲300题 》将于2024年出版,是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C++、Java、Python三种语言给出代码,以中低档题为主,适合入门、进阶。 “ 松鼠与栗子 ” ,链接: http://oj.ecustacm.cn/problem.php?id=1852 【题目描述】 现在有m棵栗

    2024年02月11日
    浏览(43)
  • 罗勇军 → 《算法竞赛·快冲300题》每日一题:“排列变换” ← 贪心算法

    【题目来源】 http://oj.ecustacm.cn/problem.php?id=1812 http://oj.ecustacm.cn/viewnews.php?id=1023 【题目描述】 给定一个长度为 n 的排列 a,需要将这个排列变成 b。 每次可以选择一个数字往左移若干个位置。 请求出 最小需要移动的元素个数 。 【输入格式】 第一行为正整数 n,1≤n≤100000。

    2024年02月12日
    浏览(41)
  • 罗勇军 →《算法竞赛·快冲300题》每日一题:“乘积” ← 动态规划

    【题目来源】 http://oj.ecustacm.cn/problem.php?id=1781 http://oj.ecustacm.cn/viewnews.php?id=1023 【题目描述】 给你一个长度为 n 的序列,序列中的元素只包括 1 和 -1。 请问有多少个连续的子序列乘积为正数。 【输入格式】 输入第一行为正整数 n。(n不超过10^6) 第二行包含 n 个整数。 【输

    2024年02月11日
    浏览(52)
  • 罗勇军 →《算法竞赛·快冲300题》每日一题:“小球配对” ← 并查集

    【题目来源】 http://oj.ecustacm.cn/problem.php?id=1850 http://oj.ecustacm.cn/viewnews.php?id=1023 【题目描述】 给定 n 个小球,编号为 1-n ,给定 m 个篮子,编号为 1-m 。 每个球只允许放入样例给定的编号为 Ai 或者 Bi 的两个篮子中的 1 个。 每个球必须放入某个篮子。 如果篮子中球的数量为奇

    2024年02月11日
    浏览(40)
  • 罗勇军 →《算法竞赛·快冲300题》每日一题:“游泳” ← DFS+剪枝

    【题目来源】 http://oj.ecustacm.cn/problem.php?id=1753 http://oj.ecustacm.cn/viewnews.php?id=1023 【题目描述】 游泳池可以等分为n行n列的小区域,每个区域的温度不同。 小明现在在要从游泳池的左上角(1, 1)游到右下角(n, n),小明只能向上下左右四个方向游,不能游出泳池。 而小明对温度十分

    2024年02月10日
    浏览(38)
  • leecode 每日一题 2596. 检查骑士巡视方案

      2596. 检查骑士巡视方案 骑士在一张  n x n  的棋盘上巡视。在  有效  的巡视方案中,骑士会从棋盘的  左上角  出发,并且访问棋盘上的每个格子  恰好一次  。 给你一个  n x n  的整数矩阵  grid  ,由范围  [0, n * n - 1]  内的不同整数组成,其中  grid[row][col]  表示单

    2024年02月08日
    浏览(46)
  • 【C语言每日一题】10. 超级玛丽游戏

    题目来源:http://noi.openjudge.cn/ch0101/10/ 总时间限制: 1000ms 内存限制: 65536kB 超级玛丽是一个非常经典的游戏。请你用字符画的形式输出超级玛丽中的一个场景。 无。 如样例所示。

    2024年02月10日
    浏览(37)
  • 二叉树(中)+Leetcode每日一题——“数据结构与算法”“剑指Offer55-I. 二叉树的深度”“100.相同的树”“965.单值二叉树”

    各位CSDN的uu们你们好呀,今天继续数据结构与算法专栏中的二叉树,下面,让我们进入二叉树的世界吧!!! 二叉树(上)——“数据结构与算法”_认真学习的小雅兰.的博客-CSDN博客 二叉树链式结构的实现 二叉树链式结构的实现 求二叉树的高度 但是这种写法有很大的问题

    2024年02月17日
    浏览(41)
  • 算法|每日一题|H 指数|二分

    原题地址: 力扣每日一题:H 指数 给你一个整数数组 citations ,其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。 根据维基百科上 h 指数的定义:h 代表“高引用次数” ,一名科研人员的 h 指数 是指他(她)至少发表了 h 篇论文,并且每

    2024年02月08日
    浏览(42)
  • 每日一题之常见的排序算法

    排序是最常用的算法,常见的排序算法有冒泡排序、选择排序、插入排序、快速排序、希尔排序和归并排序。除此之外,还有桶排序、堆排序、基数排序和计数排序。 1、冒泡排序 冒泡排序就是把小的元素往前放或大的元素往后放,比较的是相邻的两个元素。 时间复杂度:

    2024年02月13日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包