最大連通

鏈接：
https://www.lanqiao.cn/problems/2410/learning/

問題描述

小藍有一個 30 行 60 列的數字矩陣，矩陣中的每個數都是 0 或 1 。

110010000011111110101001001001101010111011011011101001111110010000000001010001101100000010010110001111100010101100011110 001011101000100011111111111010000010010101010111001000010100 101100001101011101101011011001000110111111010000000110110000 010101100100010000111000100111100110001110111101010011001011 010011011010011110111101111001001001010111110001101000100011 101001011000110100001101011000000110110110100100110111101011 101111000000101000111001100010110000100110001001000101011001 001110111010001011110000001111100001010101001110011010101110 001010101000110001011111001010111111100110000011011111101010 011111100011001110100101001011110011000101011000100111001011 011010001101011110011011111010111110010100101000110111010110 001110000111100100101110001011101010001100010111110111011011 111100001000001100010110101100111001001111100100110000001101 001110010000000111011110000011000010101000111000000110101101 100100011101011111001101001010011111110010111101000010000111 110010100110101100001101111101010011000110101100000110001010 110101101100001110000100010001001010100010110100100001000011 100100000100001101010101001101000101101000000101111110001010 101101011010101000111110110000110100000010011111111100110010 101111000100000100011000010001011111001010010001010110001010 001010001110101010000100010011101001010101101101010111100101 001111110000101100010111111100000100101010000001011101100001 101011110010000010010110000100001010011111100011011000110010 011110010100011101100101111101000001011100001011010001110011 000101000101000010010010110111000010101111001101100110011100 100011100110011111000110011001111100001110110111001001000111 111011000110001000110111011001011110010010010110101000011111 011110011110110110011011001011010000100100101010110000010011 010011110011100101010101111010001001001111101111101110011101

如果從一個標為 1 的位置可以通過上下左右走到另一個標為 1 的位置，則稱兩個位置連通。與某一個標為 1 的位置連通的所有位置（包括自己）組成一個連通分塊。

請問矩陣中最大的連通分塊有多大？

答案提交

這是一道結果填空的題，你只需要算出結果后提交即可。本題的結果為一個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分。

運行限制

• 最大運行時間：1s
• 最大運行內存: 256M

思路

這題就是很明顯的dfs。

這道題的題意就是，讓我們找一個全為1的連通分塊，因為會有很多種連通分塊，我們只需要找到最長的，即含1最多的連通分塊就可以，然后把1的個數輸出即可。

就是我覺得這種需要你上下左右去遍厲二維數組的dfs題，一般都是以下思路(一般迷宮類的好像都是這么個思路)：

??????? 首先需要創建一個boolean[][]b數組，用來標記(i,j)這個點是否被訪問過。也可以用int型的數組代替，0-未訪問過，1-訪問過。然后再創建存方向的二維數組f[][]，一般用{{0,1},{0,-1},{1,0},{-1,0}}來表示下、上、右、左四個方向。然后還需要一個存題中數據的一個二維數組g[][]。然后還需要一個變量ans來存最終的結果。大體都是需要這些東西的，根據題意靈活變通即可。

然后下面來說一下這一題的思路：

??????? 首先它dfs的思路是什么，就是我們先找一個切入點，這題比較特殊，這個切入點的值需要是'1'，才有可能找到一個連通分塊，如果切入點就是'0'，那根本往下走不了了啊，剛開始就不滿足條件了。所以在進行dfs之前，我們先遍厲一下二維數組g[][]，如果g[i][j]=='1'&&b[i][j]==false，就說明點(i,j)就可以作為切入點。然后我們就可以從這個(i,j)點開始dfs。

??????? 那么dfs該怎么寫？

??????? 通常來說dfs在這種矩陣題里面一般都是傳兩個參數，即x，y坐標，dfs(int x, int y)。然后dfs里大多數都會寫這么一個判斷條件，就是判斷是否越界，如果越界了，我們直接return即可。如果沒越界，我們就讓b[x][y]為true，即我現在從(x,y)開始dfs，那么(x,y)這個點相當于我訪問過了。然后我們就利用方向數組f[][]，去在(x,y)這個點上去枚舉上、下、左、右四種方向，然后每枚舉一個方向，我們就用兩個臨時變量tx,ty去存儲執行完該方向的坐標，同時還要再次判斷更新后的坐標是否越界，是否被訪問過，是否為'1'，只有不越界、沒被訪問過、為''1，才能繼續從這個點(tx,ty)進行進一步的dfs。

??????? 由于我通常把ans設成static，所以dfs執行完之后，ans也就更新好了，在main里面直接輸出即可。

最大連通-代碼

import java.util.Scanner;
public class Main {static boolean [][] b = new boolean[30][60];  // 默認全為falsestatic char [][]g = new char[30][60];static int [][]f = {{0,-1},{0,1},{-1,0},{1,0}}; // 上 下 左 右static int cnt = 0;public static void main(String[] args) {String []s = {"110010000011111110101001001001101010111011011011101001111110","010000000001010001101100000010010110001111100010101100011110","001011101000100011111111111010000010010101010111001000010100","101100001101011101101011011001000110111111010000000110110000","010101100100010000111000100111100110001110111101010011001011","010011011010011110111101111001001001010111110001101000100011","101001011000110100001101011000000110110110100100110111101011","101111000000101000111001100010110000100110001001000101011001","001110111010001011110000001111100001010101001110011010101110","001010101000110001011111001010111111100110000011011111101010","011111100011001110100101001011110011000101011000100111001011","011010001101011110011011111010111110010100101000110111010110","001110000111100100101110001011101010001100010111110111011011","111100001000001100010110101100111001001111100100110000001101","001110010000000111011110000011000010101000111000000110101101","100100011101011111001101001010011111110010111101000010000111","110010100110101100001101111101010011000110101100000110001010","110101101100001110000100010001001010100010110100100001000011","100100000100001101010101001101000101101000000101111110001010","101101011010101000111110110000110100000010011111111100110010","101111000100000100011000010001011111001010010001010110001010","001010001110101010000100010011101001010101101101010111100101","001111110000101100010111111100000100101010000001011101100001","101011110010000010010110000100001010011111100011011000110010","011110010100011101100101111101000001011100001011010001110011","000101000101000010010010110111000010101111001101100110011100","100011100110011111000110011001111100001110110111001001000111","111011000110001000110111011001011110010010010110101000011111","011110011110110110011011001011010000100100101010110000010011","010011110011100101010101111010001001001111101111101110011101"};for(int i = 0;i < 30;i ++) {for(int j = 0;j < 60;j ++) {g[i][j] = s[i].charAt(j);}}// 找一個可以切入的點int ans = 0;for(int i = 0;i < 30;i ++) {for(int j = 0;j < 60;j ++) {cnt = 0;if (g[i][j] == '1' && !b[i][j]) {dfs (i,j);}ans = Math.max(ans,cnt);}}System.out.println(ans);    // ans = 148}public static void dfs (int x, int y) {cnt ++;if (x < 0 || x >= 30 || y < 0 || y >= 60 || g[x][y] == '0' || b[x][y]) {return; // 不滿足dfs條件}// 這就可以開始正式的dfsb[x][y] = true;// 遍厲四個方向，看看有沒有可通的路for(int i = 0;i < 4;i ++) {int tx = x + f[i][0];int ty = y + f[i][1];if (tx >= 0 && tx < 30 && ty >= 0 && ty < 60 && g[tx][ty] == '1' && !b[tx][ty]) {dfs (tx , ty);}}}
}

五子棋對弈

鏈接：https://www.lanqiao.cn/problems/19694/learning/=

?問題描述

"在五子棋的對弈中，友誼的小船說翻就翻？" 不！對小藍和小橋來說，五子棋不僅是棋盤上的較量，更是心與心之間的溝通。這兩位摯友秉承著"友誼第一，比賽第二"的宗旨，決定在一塊 5×5 的棋盤上，用黑白兩色的棋子來決出勝負。但他們又都不忍心讓對方失落，于是決定用一場和棋（平局）作為彼此友誼的見證。

比賽遵循以下規則：

1. 棋盤規模：比賽在一個 5×5 的方格棋盤上進行，共有 25 個格子供下棋使用。
2. 棋子類型：兩種棋子，黑棋與白棋，代表雙方。小藍持白棋，小橋持黑棋。
3. 先手規則：白棋（小藍）具有先手優勢，即在棋盤空白時率先落子（下棋）。
4. 輪流落子：玩家們交替在棋盤上放置各自的棋子，每次僅放置一枚。
5. 勝利條件：率先在橫線、豎線或斜線上形成連續的五個同色棋子的一方獲勝。
6. 平局條件：當所有 25 個棋盤格都被下滿棋子，而未決出勝負時，游戲以平局告終。

在這一設定下，小藍和小橋想知道，有多少種不同的棋局情況，既確保棋盤下滿又保證比賽結果為平局。

答案提交

這是一道結果填空題，你只需要算出結果后提交即可。本題的結果為一個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分。

運行限制

語言	最大運行時間	最大運行內存
C++	1s	256M
C	1s	256M
Java	3s	512M
Python3	10s	512M
PyPy3	3s	512M
Go	5s	512M
JavaScript	5s	512M

思路

????????這一題也是矩陣那種的，但是它和上一題最大連通還有點不一樣。

????????但是我又說不清具體有什么區別。我的理解就是，最大連通那題它dfs路徑我們是不可預知的，也就是說它可以隨意拐彎，所以我們只有通過設置四個方向去這樣遍厲，才能夠找到所有可能的結果。

??????? 但是這道題不太一樣，因為五子棋對弈這道題它的矩陣大小是5x5，這樣五子棋勝利的情況就直接被限定死了，只有豎著5顆同色棋子、橫著5顆同色棋子、對角線5顆同色棋子。也就是有這3大類的情況(橫、豎、斜)，所以我覺得這種類型我們也沒有設置方向的必要。我們可以直接按照橫、豎、斜三種方向分類就行，判斷有沒有人獲勝就行。那么怎么判斷？？？

??????? 所以這一類的dfs就需要一個check()函數，去判斷有沒有人獲勝。如果check為true，就說明是平局，也有了一種答案；為false就不可以，就說明肯定有人贏了。

??????? 那么如何設計check()？

??????? 因為題目要求是平局，所以我們在dfs中直接判斷贏的情況，只要贏了，就直接返回false。只有3大類情況都沒有人贏，我們才能返回true，然后我們讓答案ans++。

??????? dfs里面需要check()函數，那么dfs的其他部分該怎么寫呢？

??????? 因為題目中白棋先手，所以自始至終棋盤上的白棋數都會比黑棋數多一，因為總共是5x5，所以平局總共就有25個子，易得白棋最多13個，黑棋最多12個。知道黑白棋數的關系，下面我們就該想一想，怎么下棋？

??????? 下棋肯定需要棋盤和棋子的坐標，那么坐標怎么求？

??????? 棋盤我們設為g[][]，g = 1為黑子，g = 0為白子。然后下面求每個棋子對應的坐標，設num為棋盤上的總棋子數，所以很容易求得，坐標x為num/5，坐標y為num%5。然后知道坐標之后就可以開始下棋，設白棋數為w，黑棋數為b，如果w < 13，我們就下白子，dfs(num+1，w+1, b)；如果b < 12就下黑子，dfs(num + 1, w, b + 1)。兩個dfs全部執行完之后，所有可能的棋盤方案數也就枚舉完成了。當num == 25的時候，我們就用check()判斷一下就行，true就ans++，false就直接return。

五子棋對弈-代碼

感覺這題還是講的不明白，還沒理解到精華部分，一表述出來就會冒很多問題。。。。。。

如果看不懂可以直接看代碼，代碼我覺得還挺好理解的。

import java.util.Scanner;
public class Main {static int[][]g = new int[5][5];static int ans = 0;static boolean[][]b = new boolean[5][5];public static void main(String[] args) {dfs(0,0,0);System.out.println(ans);  // ans = 3126376}public static void dfs(int num,int w,int b) {   // num棋盤上總棋子數, w白子個數, b黑子個數if (num == 25) {if (check()) {ans ++;}return;}// 找到每個棋子對應的坐標int x = num / 5;int y = num % 5;// 開始下棋子if (w < 13) { // 白棋先手，所以最終會比黑棋多1個g[x][y] = 0;  // 下白子dfs(num + 1,w + 1,b);}if (b < 12) {g[x][y] = 1;  // 下黑子dfs(num + 1,w,b + 1);}}public static boolean check () {   // 判斷是否有人勝出，應該是沒人勝出ans才加1// 檢查棋盤// 先判斷行、列有沒有連成線的for(int i = 0;i < 5;i ++) {int rcnt = 0; // 統計行上邊有沒有連成線的int ccnt = 0; // 統計列上邊有沒有連成線的for(int j = 0;j < 5;j ++) {rcnt += g[i][j];ccnt += g[j][i];}if (rcnt == 0 || ccnt == 5) {return false; // 有人勝出}if (rcnt == 5 || ccnt == 0) {return false;}}// 判斷對角線上邊int d1 = 0;int d2 = 0;for(int i = 0;i < 5;i ++) {d1 += g[i][i];d2 += g[i][4-i];}if (d1 == 0 || d2 == 5) {return false;}if (d1 == 5 || d2 == 0) {return false;}return true;}
}

分糖果

鏈接：https://www.lanqiao.cn/problems/4124/learning/

問題描述

兩種糖果分別有 9 個和 16 個，要全部分給 7 個小朋友，每個小朋友得到的糖果總數最少為 2 個最多為 5 個，問有多少種不同的分法。糖果必須全部分完。

只要有其中一個小朋友在兩種方案中分到的糖果不完全相同，這兩種方案就算作不同的方案。

答案提交

這是一道結果填空的題，你只需要算出結果后提交即可。本題的結果為一個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分。

運行限制

• 最大運行時間：1s
• 最大運行內存: 256M

思路

這題我感覺是一維的dfs，甚至都沒用到數組。

????????題意就是讓你把兩種糖果分給7個小朋友，每個小朋友只能得到2-5個糖果，且糖果必須全部分完，讓你求可行的方案數。

??????? 我感覺這題的代碼可能算不上dfs，通俗點來說應該是的完完全全的暴力。

??????? 先看那個dfs()的思路，我們傳進去的參數是i，表示在給第i個小朋友分糖果。那么如果i>n(小朋友總數)，就說明我們已經給7個小朋友分完糖果了，但是分完糖果就完事了嗎？答案是否定的。我們還需判斷兩種糖果是否有剩余，只有他們全為0的時候，才說明是全分完的，我們才能讓ans++。然后我們還要判斷是否有越界的，就是糖果不能一直往下減，如果有一個減到0以下了，我們就直接return。最后那個for循環就是dfs的核心，j表示我們給第i個小朋友總共發了j個糖果，然后里面的k表示，第一種糖果我給了第i個小朋友k個，那么第二種糖果很顯然就給了j-k個。如果運行完b-=j-k這一行代碼，就說明第i個小朋友我們已經完成分配糖果的任務了，所以我們直接再給下一個小朋友i+1進行分配dfs(i+1);但是要注意我們dfs(i+1)之后還要恢復，因為有可能dfs(i+1)是不滿足的，所以我們還需要從第i個狀態去遍厲dfs另一條分支。
??????? 最后輸出結果ans就可以了。

分糖果-代碼

import java.util.Scanner;public class Main {static int a = 9;static int b = 16;static int n = 7;static int ans = 0;public static void main(String[]args) {dfs (1);System.out.println(ans);}public static void dfs (int i) {if (i > n) {if (a == 0 & b == 0) {ans ++;}return;}if (a < 0 || b < 0) {return;}for(int j = 2;j <= 5;j ++) {for(int k = 0;k <= j;k ++) {a -= k;b -= j - k;dfs (i + 1);a += k;b += j - k;}}}
}

飛機降落

鏈接：https://www.lanqiao.cn/problems/3511/learning/

問題描述

N 架飛機準備降落到某個只有一條跑道的機場。其中第 i 架飛機在 Ti 時刻到達機場上空，到達時它的剩余油料還可以繼續盤旋 Di 個單位時間，即它最早可以于 Ti 時刻開始降落，最晚可以于 Ti+Di 時刻開始降落。降落過程需要 Li 個單位時間。

一架飛機降落完畢時，另一架飛機可以立即在同一時刻開始降落，但是不能在前一架飛機完成降落前開始降落。

請你判斷 N 架飛機是否可以全部安全降落。

輸入格式

輸入包含多組數據。

第一行包含一個整數 T ，代表測試數據的組數。

對于每組數據，第一行包含一個整數 N 。

以下 N 行，每行包含三個整數：Ti ?，Di 和 Li 。

輸出格式

對于每組數據，輸出 YES? 或者 NO ，代表是否可以全部安全降落。

樣例輸入

2
3
0 100 10
10 10 10
0 2 20
3
0 10 20
10 10 20
20 10 20

樣例輸出

YES
NO

樣例說明

對于第一組數據，可以安排第 3 架飛機于 0 時刻開始降落，20 時刻完成降落。安排第 2 架飛機于 20 時刻開始降落，30 時刻完成降落。安排第 1 架飛機于 30 時刻開始降落，40 時刻完成降落。

對于第二組數據，無論如何安排，都會有飛機不能及時降落。

評測用例規模與約定

對于 30% 的數據，N≤2N≤2。

對于 100% 的數據，1≤T≤10 ，1≤N≤10 ，0≤Ti,Di,Li≤10^5 。

運行限制

語言	最大運行時間	最大運行內存
C++	2s	256M
C	2s	256M
Java	3s	256M
Python3	4s	256M
PyPy3	4s	256M
Go	4s	256M
JavaScript	4s	256M

思路

????????這道題其實和五子棋對弈那題有一點點相似，就是它不是傳統的那種走迷宮形式的dfs，所以這種題目dfs傳進去的參數就比較靈活，也需要我們好好的考慮以下如何進行dfs。

??????? 這道題我一開始做的時候也沒有思路，還以為是貪心。后來看了大佬們的題解就恍然大悟，也才意識到dfs傳進去的參數是多么的靈活。

??????? 首先這道題的題意就是，根據給你的N架飛機的到達機場時間、盤旋時間以及降落所需時間，去判斷，存不存在一種合理的方式，能夠讓這N架飛機降落成功。所謂的降落成功就是題目中的：一架飛機降落完畢時，另一架飛機可以立即在同一時刻開始降落，但是不能在前一架飛機完成降落前開始降落。

??????? 所以題意還是挺好理解的，下面的重點就是，我們怎么用代碼去找合理的降落順序？

??????? 我們先想一想，我們用什么去衡量能不能讓當前飛機開始降落？答案很顯然，應當是總時間。就是當前飛機的到達時間 + 當前飛機的盤旋時間 >= 前面飛機降落完成的時間，即總時間為前面飛機降落完成的時間。如果滿足這個條件：當前飛機的到達時間 + 當前飛機的盤旋時間 >= 前面飛機降落完成的時間，那么當前飛機是一定可以降落的，只不過當前飛機降落完成的時間會不一定而已。為什么這么說？因為如果當前飛機到達的時候，就已經大于前一個飛機降落完成的時間了，那么這架飛機一到這就可以直接降落，所以這架飛機降落完的時間就是這架飛機的到達時間+當前飛機降落所需時間；如果當前飛機到達的時候，前面的飛機正在降落，那么我們就要先盤旋一會，所以最終當前飛機降落完成的時間就是，前一架飛機降落完成的時間+這架飛機的降落時間。所以在dfs傳進去的參數中，我們要傳一個x，表示這是第幾架飛機；還要傳一個totalTime，表示總時間。最開始就從dfs(0,0)開始就可以，如果dfs里面的x能夠等于N，就說明能夠合理安排這N架飛機，返回true，打印YES；反之，返回false，打印NO。

飛機降落-代碼

import java.util.Scanner;
public class Main {static int N,T;static boolean flag ;static int[]t;  // 到達機場時間static int[]d;  // 盤旋時間static int[]l;  // 降落所需時間static boolean[]b;public static void main(String[] args) {Scanner sc = new Scanner(System.in);T = sc.nextInt();while(T-- > 0) {N = sc.nextInt();t = new int[N];d = new int[N];l = new int[N];b = new boolean[N];for(int i = 0;i < N;i ++) {t[i] = sc.nextInt();d[i] = sc.nextInt();l[i] = sc.nextInt();}dfs(0,0);if (flag) {System.out.println("YES");}else {System.out.println("NO");}flag = false; // 因為是多組輸入，最后重置一下flag，設成默認值false}}public static void dfs (int x, int totalTime) {if (x == N) {flag = true;return;}for(int i = 0;i < N;i ++) {if (b[i]) {continue;}b[i] = true;if (t[i] + d[i] >= totalTime)  {  // 到達時間 + 盤旋時間 >= 上一架飛機的'完成'降落時間   就可以降落if (t[i] > totalTime) {   // 到達時間 > 前一個飛機完成降落的時間dfs(x+1,t[i] + l[i]);   // 判斷下一架飛機 , 時間更新為飛機x+1到達時間 + 對應的降落時間。因為這種情況它是到這就能飛的，所以直接用到達時間加就可以。}else if (t[i] <= totalTime) {dfs(x+1,totalTime + l[i]);  // 這種就是到達時間 <= 前一個飛機完成降落的時間，所以我們要等前一個飛機飛完，即等到totalTime就可以，然后加上飛機x+1的降落時間即可。}}b[i] = false;  // 回溯取消標記}}
}