NENU OJ算法2例題

合集原文指路

算法2搜索E

1281: E001 數的劃分

題目描述

將整數n分成k份，且每份不能為空，任意兩種分法不能相同（不考慮順序）。
例如：n=7，k=3，下面三種分法被認為是相同的。
1,1,5；1,5,1；5,1,1；
問有多少種不同的分法。

輸入

每組數據由一行上的2個整數n，k構成（6<n≤200,2≤k≤6）。

輸出

對每組測試數據，輸出不同的分法整數。

樣例輸入

7 3

樣例輸出

4

AC代碼

#include<bits/stdc++.h>
#define AUTHOR "DODOLA"
using namespace std;
typedef long long ll;
const int maxn = 220;
ll dp[maxn][maxn];  // i個小球放入j個盒子沒有空盒的方法數
int main() {int n, k;cin >> n >> k;for (int i = 1;i <= n;i++) {dp[i][1] = 1;dp[i][0] = 1;}for (int i = 2;i <= n;i++) {for (int j = 2;j <= k;j++) {if (i > j)dp[i][j] = dp[i - 1][j - 1] + dp[i - j][j];elsedp[i][j] = dp[i - 1][j - 1];}}cout << dp[n][k] << endl;return 0;
}

1282: E002 閃避湖泊

題目描述

農夫約翰的農場在最近的一場暴風雨中被水淹沒。但保險公司僅根據他得農場中最大的“湖泊”的大小賠償一個數額。
農場可表示為N行M列的長方形網格，（1≤N≤100,1≤M≤100）。網格中的每個單元或是干的或是被淹沒的，且恰有K個單元被水淹沒，（1≤K≤N*M）。正如人們所希望的，湖泊是一個中間單元，它與其他的單元共享一條長邊（不是角落）。任何與中間單元共享一條長邊或者與連通單元共享一條長邊的單元是一個連通單元，是湖泊的一部分。

輸入

有多組數據。每組的第1行有3個整數N，M和K。第2行到第K+1行，是整數R和C，表示被淹沒的位置。

輸出

對每組測試數據，輸出有最大湖泊的單元的數目。

樣例輸入

3 4 5
3 2
2 2
3 1
2 3
1 1

樣例輸出

4

AC代碼

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 150;int n, m, k;
bool fd[maxn][maxn];
int mv[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };int ans;
int dfs(int r, int c) {if (r<1 || r>n || c<1 || c>m || !fd[r][c])return 0;fd[r][c] = false;int ret = 1;for (int i = 0;i < 4;i++) {ret += dfs(r + mv[i][0], c + mv[i][1]);}return ret;
}void solve() {fill(fd[0], fd[0] + maxn * maxn, false);ans = 0;for (int ki = 0;ki < k;ki++) {int r, c;cin >> r >> c;fd[r][c] = true;}for (int i = 1;i <= n;i++) {for (int j = 1;j <= m;j++) {if (fd[i][j]) {ans = max(ans, dfs(i, j));}}}cout << ans << "\n";
}int main() {while (cin >> n >> m >> k)solve();return 0;
}
/*
0 1 0 0 0
0 0 1 1 0
0 1 1 0 0
*/

1283: E003 信道分配

題目描述

當無線電臺在一個非常大的區域上傳播信號時，為了每個接收器都能得到較強信號，使用轉發器轉發信號。然而，需要仔細地選擇每個轉發器使用的頻道，以使附近的轉發器不彼此干擾。如果鄰近的轉發器使用不同的頻道，條件就得到滿足。
因為無線電波的頻譜是寶貴的資源，轉發器所需頻道的數量應減到最少。編程任務：讀取轉發器網絡的描述信息，并計算出所需頻道的最小使用量。

輸入

輸入包含許多轉發器網絡圖。每幅圖的第一行是轉發器數目（1~26）。轉發器用連續的大寫字母表示，從A開始。例如，10個轉發器的名稱分別是A，B，C，…，I和J。當轉發器的個數是0時，表示輸入結束。
轉發器數目之后，是其鄰近關系的列表。每行的格式為
A：BCDH
表示轉發器B、C、D和H與轉發器A鄰近。第一行描述與轉發器A鄰近的，第二行描述與B鄰近的，直到描述完所有的轉發器。如果某個轉發器不與其他轉發器相鄰，它的形式為
A：
轉發器依字母順序列出。
注意：相鄰是對稱的關系；如果A與B相鄰，那么B與A也相鄰。因為轉發器位于水平面內，由相鄰的轉發器構成的網絡圖沒有相交的線。

輸出

對于每幅圖（除了最后一個沒有轉發器），輸出一行，是轉發器不互相干擾所需的最少頻道數。輸出格式參考樣例輸出。注意：頻道數為1的話，“channel”為單數。

樣例輸入

2
A:
B:
4
A:BC
B:ACD
C:ABD
D:BC
0

樣例輸出

1 channel needed.
3 channels needed.

AC代碼

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 120;
bool fd[maxn][maxn];
int ind[30], t;
bool dfs(int from, int clr) {// 從from著色for (int i = 0;i < clr;i++) {bool f = true;ind[from] = i;for (int j = 0;j < from;j++) {if (ind[j] == i && fd[from][j]) {f = false;break;}}if (f && (from == t - 1 || dfs(from + 1, clr)))return true;}return false;
}int main() {while (cin >> t) {cin.get();if (t == 0)break;memset(fd, 0, sizeof(fd));memset(ind, 0, sizeof(ind));bool f = true;for (int i = 0;i < t;i++) {string msg;cin >> msg;if (msg.size() == 2)continue;f = false;int pid = msg[0] - 'A';for (int j = 2;j < msg.size();j++) {fd[pid][msg[j] - 'A'] = true;fd[msg[j] - 'A'][pid] = true;}}if (f)cout << "1 channel needed.\n";else if (dfs(1, 2))cout << "2 channels needed.\n";else if (dfs(1, 3))cout << "3 channels needed.\n";elsecout << "4 channels needed.\n";}return 0;
}

1284: E004 移動的騎士

題目描述

你的一個朋友正在研究騎士旅行問題（TKP）。在一個有n個方格的棋盤上，你得找到一條最短的封閉騎士旅行的路徑，使能夠遍歷每個方格一次。他認為問題的最困難部分在于，對兩個給定的方格，確定騎士移動所需的最小步數。所以你幫助他編寫一個程序，解決這個“困難的”部分。你的任務是：輸入有兩個方格a和b，確定騎士在最短路徑上從a到b移動的次數。

國際象棋中的騎士在棋盤上可移動的范圍如下圖：

輸入

輸入包含一組或多組測試例。每個測試例一行，是兩個方格，用空格隔開。棋盤上的一個方格用一個字符串表示，字母（a-h）表示列，數字（1-8）表示行。

輸出

對每個測試例，輸出一行：“To get from xx to yy takes n knight moves.”。

樣例輸入

e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6

樣例輸出

To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.

AC代碼

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 150;string fs, ts;
int mv[8][2] = { {-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1} };void bfs(int x1, int y1, int x2, int y2) {if (x1 == x2 && y1 == y2) {cout << "To get from " << fs << " to " << ts << " takes 0 knight moves.\n";return;}int stp = 0;queue<pair<int, int>> q;q.push({ x1, y1 });while (!q.empty()) {queue<pair<int, int>> qs;while (!q.empty()) {auto [x, y] = q.front();q.pop();for (int i = 0;i < 8;i++) {int nx = x + mv[i][0], ny = y + mv[i][1];if (nx < 0 || nx >= 8 || ny < 0 || ny >= 8)continue;if (nx == x2 && ny == y2) {cout << "To get from " << fs << " to " << ts << " takes " << stp + 1 << " knight moves.\n";return;}qs.push({ nx, ny });}}stp++;q = qs;}}void solve() {int x1 = fs[0] - 'a', y1 = fs[1] - '1', x2 = ts[0] - 'a', y2 = ts[1] - '1';bfs(x1, y1, x2, y2);
}int main() {while (cin >> fs >> ts)solve();return 0;
}

1285: E005 圖像周長

題目描述

病理學實驗室的技術人員需要分析幻燈片的數字圖像。幻燈片上有許多要分析的目標，由鼠標單擊確定一個目標。目標邊界的周長是一個有用的測量參數。編程任務：確定選中目標的在周長。
數字化的幻燈片是一個矩形的網格，里面有點’.’，表示空的地方；有大寫字母‘X’，表示目標的一部分。簡單網格如下所示

方格中的一個X是指一個完整的網絡方形區域，包括其邊界和目標本身。網格中心的X與其邊界上8個方向的X都是相鄰的。任何兩個相鄰的X，其網格方形區域在邊界或者拐角處是重疊的，所以他們的網格方形區域是相鄰的。
一個目標是由一系列相鄰X的網格方形區域連接起來構成的。在網格1中，一個目標填充了全部網格；在網格2中有兩個目標，其中一個目標只占左下角的一個網格方形區域，其余的X屬于另一個目標。
技術人員總是能單擊到一個X，以選中包含該X的目標，記錄單擊時的坐標。行列號是從左上角開始，從1開始編號的。在網格1中，技術人員可以單擊行2和列2選擇目標；在網格2中，單擊行2和列3就可以選中較大目標，單擊行4和列3就不能選中任何目標。
一個有用的統計參數是目標的周長。假定每個X的每條邊上有一個方形的單元。在網格1中目標的周長是8（4個邊，每個邊上有2個方形的單元）；在網格2中，較大目標的周長是18，如下圖所示。

目標中不會包含任何完全封閉的孔，所以下面最左邊的網格不會出現，應該是右邊的網格樣式。

輸入

輸入有多組網格。對每個網格，第一行是網格的行列數（rows，columns），鼠標單擊的行列號（row，column），其整數范圍都是1-20.接下來就是rows行，由字符‘.’和‘X’構成。
當一行是4個0時，標志輸入結束。一行中的4個數字之間各有一個空格。網格數據的行之間沒有空行。

輸出

對每個網絡輸出一行，是選中目標的周長。

樣例輸入

2 2 2 2
XX
XX
6 4 2 3
.XXX
.XXX
.XXX
...X
..X.
X...
5 6 1 3
.XXXX.
X....X
..XX.X
.X...X
..XXX.
0 0 0 0

樣例輸出

8
18
40

AC代碼

#include<bits/stdc++.h>
#define AUTHOR "DODOLA"
// #include<queue>
// #include<iostream>
// #include<string>
using namespace std;
const int maxn = 250;
typedef long long ll;
int r, c, x, y;
vector<string>mp(maxn);int mv[8][2] = {{1,0},{0,1},{-1,0},{0,-1},{1,1},{1,-1},{-1,-1},{-1,1},
};
int ans;
bool ck[maxn][maxn];void dfs(int px, int py) {// cout << px << " " << py << endl;// cout << ans << endl;if (mp[px][py] != 'X' || ck[px][py])return;ck[px][py] = true;for (int j = 0;j < 4;j++) {int xj = px + mv[j][0], yj = py + mv[j][1];if (mp[xj][yj] != 'X')ans++;}for (int i = 0;i < 8;i++) {int xi = px + mv[i][0];int yi = py + mv[i][1];dfs(xi, yi);}
}string s0('.', maxn - 1);
void solve() {ans = 0;fill(ck[0], ck[0] + sizeof(ck), false);fill(mp.begin(), mp.end(), s0);for (int i = 1;i <= r;i++) {cin >> mp[i];mp[i] = " " + mp[i] + " ";}dfs(x, y);cout << ans << "\n";
}int main() {mp[0] = s0;while (cin >> r >> c >> x >> y) {if (!r && !c && !x && !y)break;solve();}return 0;
}

1286: E006 移動的騎士

題目描述

Somurolov先生是一個國際象棋高手，他聲稱在棋盤上將騎士棋子從一點移動到另外一點，沒有人比他快，你敢挑戰他嗎？
你的任務是編程計算出將一個騎士棋子從一點移動到另外一點，最少需要移動的步數。顯而易見，這樣你就有贏得Somurolov先生的機會。國際象棋中的騎士在棋盤上可移動的范圍如下圖：

輸入

首先輸入測試樣例的個數n。接下來是n組輸入數據，每組測試數據由三行整數組成：第一行是棋盤的邊長l (4 <= l <= 300)，整個棋盤的面積也就是 ll；第二行和第三行分別是騎士棋子的初始位置和目標位置，表示為整數對形式{0, …, l-1}{0, …, l-1}。保證棋子的初始和目標位置是棋盤上的合法位置。

輸出

對于每一個輸入的測試樣例，請你算出騎士從初始位置移動到目標位置最小移動步數。如果初始位置和目標位置相同，那么騎士移動的距離就是0。最后單獨一行輸出所求距離。

樣例輸入

1
8 0 0
7 0

樣例輸出

5

AC代碼

#include <iostream>
#include <queue>
#include <cstring>
#define AUTHOR "DODOLA"
using namespace std;struct P {int x;int y;int step;
};int mv[8][2] = {{1, 2}, {2, 1}, {-1, 2}, {-2, 1},{1, -2}, {2, -1}, {-1, -2}, {-2, -1}
};int bfs(int n, int x1, int y1, int x2, int y2)
{if (x1 == x2 && y1 == y2){return 0;}bool gnd[n][n];queue<P> q;memset(gnd, 0, sizeof(gnd));P start, node;start.x = x1;start.y = y1;start.step = 0;q.push(start);while (!q.empty()) {int x0, y0, step;start = q.front();q.pop();x0 = start.x;y0 = start.y;step = start.step;for (int j = 0; j < 8; j++) {int x3 = x0 + mv[j][0];int y3 = y0 + mv[j][1];if (x3 == x2 && y3 == y2)return step + 1;if (x3 >= 0 && x3 < n && y3 >= 0 && y3 < n && !gnd[x3][y3]) {node.x = x3;node.y = y3;node.step = step + 1;q.push(node);gnd[x3][y3] = 1;}}}return 0;
}int main() {int t;cin >> t;while (t--) {int x1, y1, x2, y2, n;cin >> n >> x1 >> y1 >> x2 >> y2;cout << bfs(n, x1, y1, x2, y2) << endl;}return 0;
}

1287: E007 尋找M

題目描述

給出一個整數n，編程求出一個非零整數m，使得m是n的倍數，并且m的十進制表示中只有1和0。給出的n不大于200并且肯定存在對應的m，m是十進制數并且不大于100位。

輸入

輸入包含多組測試數據。每組測試數據只有一個整數n (1 <= n <= 200)。整數0標志輸入的結束。

輸出

對于每個n輸出對應的整數m，m的十進制表示不多于100位。如果對于一個n存在多個合法的m，你只需輸出一個即可。

樣例輸入

2
6
0

樣例輸出

10
1110

AC代碼

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 10;
int n;bool ck(int x) {while (x) {if (x % 10 == 0 || x % 10 == 1) {x /= 10;continue;}else return false;}return true;
}void solve() {for (int i = 1;;i++) {int m = i * n;bool f = ck(m);if (f) {cout << m << endl;return;}}
}int main() {while (cin >> n) {if (n == 0)break;solve();}return 0;
}

1288: E008 紅與黑

題目描述

有一個矩形的房間，房間鋪著正方形的地磚。每個地磚被涂上紅色或者黑色。初始時你站在房間里的某個黑色地磚上，你每次只能移動到相鄰的四個地磚之一，即上下左右移動，并且你每次只能移動到黑色的地磚上，不能走到紅色地磚。
編程計算出按照上述要求你能走到的黑色地磚的個數。

輸入

輸入包含多組測試數據。每組測試數據第一行包括2個整數W和H；W和H是房間的寬度和長度，分別表示為房間的x和y坐標軸。W和H不大于20。接下來是H行每行W個地磚的房間，每個地磚表示如下：
‘.’——黑色地磚
‘#’——紅色地磚
‘@’ ——你在房間里的初始位置（房間只出現一次）。
輸入的最后一行是兩個整數0，不用處理。

輸出

對每個測試樣例，輸出一行，即你能走到的黑色地磚的個數（包括你初始站在的黑色地磚）。

樣例輸入

6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........
0 0

樣例輸出

45
59

AC代碼

#include <iostream>
#include <queue>
#include <cstring>
const int maxn = 120;
using namespace std;
int r, c;
char mp[maxn][maxn];
int mv[4][2] = {{0,1},{0,-1},{1,0},{-1,0},
};int ans;void dfs(int x, int y) {if (x < 0 || x == c || y < 0 || y == r)return;if (mp[x][y] == '#')return;ans++;mp[x][y] = '#';for (int i = 0;i < 4;i++) {int xi = x + mv[i][0];int yi = y + mv[i][1];dfs(xi, yi);}
}void solve() {ans = 0;int px, py;for (int i = 0;i < c;i++) {for (int j = 0;j < r;j++) {cin >> mp[i][j];if (mp[i][j] == '@') {px = i;py = j;}}}dfs(px, py);cout << ans << endl;
}int main() {while (cin >> r >> c) {if (!r && !c)break;solve();}return 0;
}

1289: E009 小木棒

題目描述

George有一些長度相等的木棒，他隨意的將這些木棒切成長度最多是50的小木棒。麻煩來了，他現在想將這些雜亂的小木棒恢復到原來的木棒，但是他忘記了原來到木棒的數量和長度。請你幫助他設計一個程序計算出原來木棒可能的最小長度，所有小木棒的長度均表示為大于0的整數。

輸入

每組輸入數據包括兩行。第一行是George切后小木棒的個數，最多有64根小木棒；第二行是這些小木棒的長度，這些長度表示為空格分開的整數。輸入樣例以整數0表示結束。

輸出

輸出一行，即為原始木棒可能的最小長度。

樣例輸入

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

樣例輸出

6
5

AC代碼

#include<bits/stdc++.h>
using namespace std;
const int maxn = 80;int n, a[maxn], maxv, tot, vis[maxn], k, len;bool cmp(int a, int b) {return a > b;
}
bool dfs(int i, int rest, int p) {if (i > k)return 1;int fail = 0;for (int x = p + 1;x <= n;x++) {if (!vis[x]) {if (a[x] == a[fail]) continue;if (rest > a[x]) {vis[x] = 1;bool w = dfs(i, rest - a[x], x);vis[x] = 0;if (!w) fail = x;if (w) return 1;}else if (rest == a[x]) {vis[x] = 1;bool w = dfs(i + 1, len, 0);vis[x] = 0;return w;}if (p == 0) return 0;}}return 0;
}void solve() {fill(vis, vis + n + 5, 0);maxv = tot = 0;for (int i = 1;i <= n;i++) {cin >> a[i];maxv = max(maxv, a[i]);tot += a[i];}sort(a + 1, a + 1 + n, cmp);for (len = maxv;len <= tot;len++) {if (tot % len == 0) {k = tot / len;if (dfs(1, len, 0)) {cout << len << endl;break;}}}
}int main() {while (cin >> n && n)solve();return 0;
}