2022-04-19每日刷題打卡

代碼源——每日一題

走不出的迷宮 - 題目 - Daimayuan Online Judge

有一個 H 行 W 列的迷宮（行號從上到下是 1?H，列號從左到右是 1?W），現在有一個由 . 和 # 組成的 H 行 W 列的矩陣表示這個迷宮的構造，. 代表可以通過的空地，# 代表不能通過的墻。

現在有個人從 起點 (1,1) 開始走，他每一步只能往右走一格或者往下走一格，并且他不能跨越迷宮的邊界。他會一直走，直到沒有可以走的路時停下來。

請問這個人最多可以經過多少個格子？

輸入格式
第一行兩個整數 H，W，表示迷宮有 H 行 W 列。

接下來一個 H 行 W 列的由 . 和 # 組成的矩陣，表示迷宮的構造。

注意：保證 (1,1) 的位置一定是 .。

輸出格式
一個整數，表示最多步數。

輸出格式

一個整數，表示最多步數。

樣例輸入1

3 4 .#.. ..#. ..##

樣例輸出1

4

樣例輸入2

1 1 .

樣例輸出2

1

樣例輸入3

5 5 ..... ..... ..... ..... .....

樣例輸出3

9

數據規模

對于全部數據保證 1≤H,W≤100

我采用的是dp做法，當然bfs也是可以的，但是要注意給每個位置打上標記防止走重復了。

dp數組dp[i] [j]的意思是：當走到i行j列的位置上是，走過的最長路徑長度。因為我們每次只能往左走或者往下走，這說明了我們想走到 [i] [j]只能從[i-1] [j]往下走一步得到或者從[i] [j-1]往右走一步得到，所以狀態轉移方程為：dp[i] [j]=max(dp[i-1] [j],dp[i] [j-1])+1。

但是直接這樣寫是會有問題的，我們要注意判斷一下兩個特殊性，

一是當前位置是“#”，此時這位置是無法走到的，所以dp[i] [j]就是0

二是雖然當前是“.”，但卻無法走到當前位置的情況，比如這么一個樣例：

3 10 ..#....... ##........ ..........

答案應當是2，但要是我們不判斷情況2，答案是會錯誤的，我們實際能走的地方只有左上角的地方，但是我們之前的計算方法會去計算后面的那些點，但實際上那些點是走不到的。所以我們應該判斷一下，如果上方和前方是0（即這兩處位置也走不到）那你本身也該是0。

#include<iostream> using namespace std; #include<vector> #include<algorithm> #include<math.h> #include<set> #include<numeric> #include<string> #include<string.h> #include<iterator> #include<map> #include<unordered_map> #include<stack> #include<list> #include<queue> #include<iomanip>#define endl '\n'; typedef long long ll; typedef pair<int, int> PII;char c[110][110]; PII que[10000]; int moves[110][110];int main() {cin.sync_with_stdio(false);cin.tie(0);cout.tie(0);int n, m, res = 1;string s;cin >> n >> m;for (int i = 0; i < n; i++){cin >> s;for (int j = 0; j < m; j++)c[i][j] = s[j];}moves[0][0] = 1;for (int i = 1; i < n; i++)if (c[i][0] == '.'){moves[i][0] = moves[i - 1][0] + 1;res = max(moves[i][0], res);}else break;for (int i = 1; i < m; i++)if (c[0][i] == '.'){moves[0][i] = moves[0][i - 1] + 1;res = max(res, moves[0][i]);}else break;for (int i = 1; i < n; i++)for (int j = 1; j < m; j++)if (c[i][j] == '.'){if (moves[i - 1][j] == 0 && moves[i][j - 1] == 0)continue;moves[i][j] = max(moves[i - 1][j], moves[i][j - 1]) + 1;res = max(res, moves[i][j]);}cout << res;return 0; }

石子游戲 II - 題目 - Daimayuan Online Judge

Alice 和 Bob 正在玩一個關于石頭的游戲。

共有 n 堆石頭，其中第 i 堆最初含有 ai 個石子。

他們輪流執行下列操作之一，從 Alice 開始。

把一堆奇數的石頭劈成兩堆，兩堆都不能空。

把兩堆偶數的石頭合成一堆。

不能執行任何操作的人將輸掉游戲。

假設 Alice 和 Bob 都足夠聰明，你知道誰會贏得游戲嗎？

輸入格式

第一行包含一個整數 n (1≤n≤106)

第二行包含 n 個正整數 a1,…,an (1≤a1,…,an≤109)

輸出格式

Alice 或 Bob，表示最終贏家

樣例輸入

2 2 2

樣例輸出

Alice

博弈論。

讓我們來分情況討論一下怎么樣才能贏：

一、只剩下一堆石頭，且這堆石頭是偶數。

二、剩下的石頭都是數量為1。

三、只有一個是偶數堆石頭，其它都是數量為1。

那么也就是說，我們想贏，就是把所有的偶數都合起來，奇數都切成1。然后我們來看一下步驟：

如果有n個數量為偶數的石頭，那我們將會進行n-1次操作才能把所有石頭合成一堆。

如果是奇數的石頭，我們可以先切一刀后把它變成一個1和一個偶數石頭（不一定要對半分的啊），如果還有偶數石頭，就可以把這個偶數石頭和另一堆合起來。那么看起來我們要記錄一下大于1的奇數石頭和大于0的偶數石頭的個數？

其實不用這么麻煩，你想：

如果只有一個奇數石頭，那我們alice批完一刀后就變成一個1和一個偶數石頭，bob就不能行動了。

如果只有兩個奇數石頭，那我們alic和bob各批完一刀后，變成了兩個1石頭和兩個偶數石頭，此時alice把這兩個偶數石頭合起來，bob又沒事干了。

所以其實不管奇數石頭的數量，最后都該是alice贏（除非奇數石頭全是1，那么Alice就直接輸了）。

所以我們就看偶數的情況就可以了，而偶數情況也很直觀，那就是要進行（偶數石頭數量-1）次操作，這樣我們就很容易的計算出哪個角色是完成最后一次合成操作的人。

此時我們就可以得到結論了：

大于0的偶數石頭數量為0時，只要奇數石頭有大于1的，那就是alic贏

大于0的偶數石頭數量不為0時，數量為偶數時Alice贏，反之bob贏

其它情況都是bob贏

#include<iostream> using namespace std; #include<vector> #include<algorithm> #include<math.h> #include<set> #include<numeric> #include<string> #include<string.h> #include<iterator> #include<map> #include<unordered_map> #include<stack> #include<list> #include<queue> #include<iomanip>#define endl '\n'; typedef long long ll; typedef pair<int, int> PII;inline int read() {int x = 0; char ch = getchar();while (ch < '0' || ch > '9') ch = getchar();while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();return x; }int main() {cin.sync_with_stdio(false);cin.tie(0);cout.tie(0);int n = read();int x, res = 0;bool flag = false;for (int i = 0; i < n; i++){x = read();if (x % 2 == 0)res++;if (x != 1)flag = true;}if ((res != 0 && res % 2 == 0) || (res == 0 && flag)){cout << "Alice" << endl;}else cout << "Bob" << endl;return 0; }

總結

以上是生活随笔為你收集整理的2022-04-19每日刷题打卡的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。