《算法竞赛·快冲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扩栈。文章来源:https://www.toymoban.com/news/detail-580109.html
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模板网!