《算法競賽·快沖300題》將于2024年出版，是《算法競賽》的輔助練習(xí)冊。
所有題目放在自建的OJ New Online Judge。
用C/C++、Java、Python三種語言給出代碼，以中低檔題為主，適合入門、進階。
“ 超級騎士” ，鏈接： http://oj.ecustacm.cn/problem.php?id=1810
題目描述
【題目描述】 現(xiàn)在在一個無限大的平面上，給你一個超級騎士。
?? 超級騎士有N種走法，請問這個超級騎士能否到達平面上的所有點。
?? 每種走法輸入兩個數(shù)字xx和yy，表示超級騎士可以從任意一點(x,y)走到(x+xx,y+yy)。
【輸入格式】 輸入第一行為正整數(shù)T，表示存在T組測試數(shù)據(jù)。（1≤T≤100）
?? 對于每組測試數(shù)據(jù)，第一行輸入正整數(shù)N，表示有N種走法。（1≤N≤100）
?? 接下來N行，每行兩個正整數(shù)xx和yy。（-100≤xx,yy≤100）。
【輸出格式】 對于每組測試數(shù)據(jù)，如果可以到達平面上所有點，輸出Yes，否則輸出No。。
【輸入樣例】
2
3
1 0
0 1
-2 -1
5
3 4
-3 -6
2 -2
5 6
-1 4
【輸出樣例】
Yes
No
題解
??雖然題目問能不能到達所有的點，但其實不用真的檢查是否能到所有的點。只要檢查平面上的某個特定點，如果從它出發(fā)能到達它的上、下、左、右4個點，那么推廣到任意一個點，它的上、下、左、右都能到達，整個平面就是可達的。
??題目給定-100≤xx, yy≤100，若定中心點(x, y)為(100, 100)，那么走一步最遠可到(0, 0)、(0, 200)、(200, 0)、(200, 200)，檢查以這4個點確定的區(qū)間內(nèi)所有點。最后看是否能到達(x, y)的上、下、左、右4個點。
??本題是一個簡單的遍歷問題，用BFS或DFS都行，計算復(fù)雜度就是區(qū)間內(nèi)點的數(shù)量，共200*200 = 40000個點，用BFS和DFS遍歷一次即可。不過，DFS有?？臻g的限制，本題的DFS需要用到很大的棧。為了保險，用BFS更好。
【重點】 注意DFS用到的棧大小。
C++代碼
??下面是DFS代碼，雖然簡單，也有小技巧。從中心點(X, Y)出發(fā)開始遍歷區(qū)間內(nèi)的點，在任意時刻只要發(fā)現(xiàn)(X, Y)的上、下、左、右都已到達，可立即返回“Yes”，不用再遍歷其他的點，這是剪枝的應(yīng)用，代碼第8行做這個判斷。寫DFS代碼時，一定要注意是否能剪枝。
#include<bits/stdc++.h>
using namespace std;
int n, xx[110], yy[110];
int X=100, Y=100; //中心點(X,Y)，從它出發(fā)
bool vis[210][210];
bool dfs(int x, int y){ //從(x,y)出發(fā)，把可以到達的點全部打上標(biāo)記
vis[x][y] = true; //把當(dāng)前點標(biāo)記為已達
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]; //新坐標(biāo)(nx, ny)
int ny = y + yy[i];
if(nx < 1 || nx > 200 || ny < 1 || ny > 200) continue; //判斷越界
if(vis[nx][ny]) continue; //已經(jīng)走過，不用再走
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)，從它出發(fā)
bool vis[210][210];
bool bfs(int x,int y){ //從(x,y)出發(fā)，把可以到達的點全部打上標(biāo)記
vis[x][y] = true; //把當(dāng)前點標(biāo)記為已達
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; //已經(jīng)走過，不用再走
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)，從它出發(fā)
static boolean[][] vis = new boolean[210][210];
public static boolean dfs(int x, int y) {
vis[x][y] = true; // 把當(dāng)前點標(biāo)記為已達
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]; // 新坐標(biāo)(nx, ny)
int ny = y + yy[i];
if (nx < 1 || nx > 200 || ny < 1 || ny > 200) continue; // 判斷越界
if (vis[nx][ny]) continue; // 已經(jīng)走過，不用再走
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代碼：不用擔(dān)心DFS的?？臻g問題。所以為了保險，還是用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擴棧。文章來源：http://www.zghlxwxcb.cn/news/detail-580109.html
import sys
sys.setrecursionlimit(1000000)
n = 0
xx,yy = [0] * 110, [0] * 110
X,Y = 100,100 # 中心點(X,Y)，從它出發(fā)
vis = [[False] * 210 for _ in range(210)]
def dfs(x, y): # 從(x,y)出發(fā)，把可以到達的點全部打上標(biāo)記
global vis
vis[x][y] = True # 把當(dāng)前點標(biāo)記為已達
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] # 新坐標(biāo)(nx, ny)
ny = y + yy[i]
if nx < 1 or nx > 200 or ny < 1 or ny > 200: continue # 判斷越界
if vis[nx][ny]: continue # 已經(jīng)走過，不用再走
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代碼：文章來源地址http://www.zghlxwxcb.cn/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')
到了這里，關(guān)于《算法競賽·快沖300題》每日一題：“超級騎士”的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
