poj1201思路及代码
时间: 2024-06-02 08:08:54 浏览: 11
题目描述
给出 n 个电话号码,找出其中的最长公共前缀。
输入格式
第一行包含整数 n。
接下来 n 行,每行包含一个电话号码。
输出格式
输出最长公共前缀,若不存在公共前缀则输出空字符串。
数据范围
1≤n≤10^5,电话号码的长度均不超过 100。
输入样例1
3
1234567890
123456
1234567
输出样例1
123456
输入样例2
3
1234567890
123456
2234567
输出样例2
""
C++ 代码
算法
(字符串) $O(n^2)$
C++ 代码
相关问题
poj1753解题思路
POJ1753的题目描述为:有一个4×4的棋盘,棋盘中有16个棋子,其中有14个棋子是黑色的,用B表示;另外两个棋子是白色的,用W表示。现在要求移动棋子,将两个白色棋子移到一起,移动棋子方式是把与白色棋子相邻(上下左右,而非斜向相邻)的棋子移到空位上。现在,请你求出最少需要移动多少次。
题目看起来很简单,但是要考虑各种情况,一般在处理类似的搜索问题时,我们使用Breath First Search (BFS)来解决问题。
BFS 是一种优秀的遍历搜索算法,广泛应用于许多问题,特别是计算机科学和人工智能。BFS 只需要进行一次完整的搜索即可找到问题的最短路径或解决方案。
在这道题目中,我们可以使用 BFS 来解决问题。
我们首先需要定义状态的表示方式,可以这么表示:
1. 4*4的数组board表示状态。
2. 一个结构体Node,代表搜索树的每个节点。其中状态的表示形式为board。还有一些列信息,包括横,纵坐标,深度depth,以及方向dir。
我们使用 queue 来存储每一层需要遍历的结点,对于每个结点,我们枚举它可以到达的状态,并将这些状态添加到队列中,继续进行下一层的遍历。直到达到目标状态。
因此,我们的搜索过程主要包括以下的步骤:
1. 判断当前状态是否是目标状态
2. 枚举当前状态可能到达的所有状态,并判断是否合法
3. 如果该状态未被访问过,添加该状态,进行遍历。
知道了上面的步骤,我们就可以使用 bfs 来解决问题了。
具体实现可以参考以下代码:
poj2386 解题思路
题目描述:
给定一个 $N \times M$ 的矩阵,其中 "." 表示水洼,"W" 表示水。请计算有多少个水洼。
解题思路:
这是一道非常经典的搜索题目。我们可以使用 DFS 或 BFS 进行求解。
首先,我们需要遍历整个矩阵,当我们遇到一个 "." 时,我们就从该点开始向四周搜索,将所有相邻的 "." 变为 "W" ,并继续向下搜索。每次搜索完毕后,我们就可以找到一个完整的水洼,计数器加一。最后,当我们遍历完整个矩阵后,就可以得到所有的水洼数量。
代码实现:
使用 DFS 进行搜索:
```c++
#include <iostream>
using namespace std;
const int maxn = 110;
char field[maxn][maxn];
bool vis[maxn][maxn];
int n, m;
void dfs(int x, int y) {
vis[x][y] = true;
for (int dx = -1; dx <= 1; dx++) {
for (int dy = -1; dy <= 1; dy++) {
int nx = x + dx, ny = y + dy;
if (nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny] && field[nx][ny] == '.') {
dfs(nx, ny);
}
}
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> field[i][j];
}
}
int res = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!vis[i][j] && field[i][j] == '.') {
dfs(i, j);
res++;
}
}
}
cout << res << endl;
return 0;
}
```
使用 BFS 进行搜索:
```c++
#include <iostream>
#include <queue>
using namespace std;
const int maxn = 110;
char field[maxn][maxn];
bool vis[maxn][maxn];
int n, m;
void bfs(int x, int y) {
queue<pair<int, int>> q;
q.push(make_pair(x, y));
vis[x][y] = true;
while (!q.empty()) {
int cx = q.front().first, cy = q.front().second;
q.pop();
for (int dx = -1; dx <= 1; dx++) {
for (int dy = -1; dy <= 1; dy++) {
int nx = cx + dx, ny = cy + dy;
if (nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny] && field[nx][ny] == '.') {
q.push(make_pair(nx, ny));
vis[nx][ny] = true;
}
}
}
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> field[i][j];
}
}
int res = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!vis[i][j] && field[i][j] == '.') {
bfs(i, j);
res++;
}
}
}
cout << res << endl;
return 0;
}
```
时间复杂度:
两种方法的时间复杂度均为 $O(NM)$,其中 N 和 M 分别为矩阵的行数和列数。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)