#include<stdio.h>
int n,m;
int a[1002][1002];
int b[1002][1002];//判断该空的八连通图是否被走过
int gg=0;
int dd=0;
int xz[8]={-1,-1,-1,0,0,1,1,1},yz[8]={-1,0,1,-1,1,-1,0,1};//八个方向
void dfs(int x,int y)
{
int dx,dy;
for(int i=0;i<8;i++)
{
dx=x+xz[i];
dy=y+yz[i];
if(dx>=0&&dx<n&&dy>=0&&dy<m&&a[dx][dy]==0&&b[dx][dy]==0)
{
b[dx][dy]=1;
dfs(dx,dy);
}
}
}
void ww(int x,int y)
{
for(int i=0;i<8;i++)
{
int p=x+xz[i];
int q=y+yz[i];
if(p>=0&&p<n&&q>=0&&q<m&&a[p][q]!=-1)
a[p][q]++;
}
}
int ff(int x,int y)
{
for(int i=0;i<8;i++)
{
int xx=x+xz[i];
int yy=y+yz[i];
if(xx>=0&&xx<n&&yy>=0&&yy<m&&a[xx][yy]==0)
return 0;
}
return 1;
}
int main()
{
int hh;
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
scanf("%d",&a[i][j]);
if(a[i][j]==1)
a[i][j]=-1;
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(a[i][j]==-1)
ww(i,j);
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(a[i][j]!=0&&a[i][j]!=-1&&ff(i,j))
dd++;
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(a[i][j]==0&&b[i][j]==0)
{
gg++;
dfs(i,j);
}
}
}
printf("%d",gg+dd);
return 0;
}
#include <stdio.h>
#include <string.h>
// 定义全局变量n和m，分别表示地图的行数和列数
// b数组用于标记每个位置是否已经被访问过，初始化为0表示未访问
// x1, y1, x2, y2 分别用于记录起点（Y）和终点（M）的坐标
int n, m, b[203][203] = {0}, x1, y1, x2, y2;
// 定义方向数组d，用于表示上下左右四个方向的偏移量
// 分别是向右（0, 1），向下（1, 0），向左（-1, 0），向上（0, -1）
int d[4][2] = { {0, 1}, {1, 0}, {-1, 0}, {0, -1}};
// 字符数组a用于存储地图信息
char a[203][203];
// 定义队列结构体，包含横坐标dx和纵坐标dy
struct queue {
int dx;
int dy;
} q[50000];
// 广度优先搜索函数，从坐标(x, y)开始进行搜索
// c数组用于记录从起点到各个位置的步数
void bfs(int x, int y, int c[][203]) {
// 初始化队列的头指针f和尾指针r，f指向队列头部，r指向队列尾部的下一个位置
int f = 0, r = 1;
// 将起始点的坐标存入队列
q[1].dx = x;
q[1].dy = y;
// 标记起始点已经被访问过
b[x][y] = 1;
// 当队列不为空时，进行循环
while (f < r) {
// 取出队列头部的点，头指针后移
f++;
// 计算当前位置下一步的步数，是当前位置的步数加1
int s = c[q[f].dx][q[f].dy] + 1;
// 尝试向四个方向进行扩展
for (int i = 0; i < 4; i++) {
// 计算扩展后的新坐标
int nx = q[f].dx + d[i][0];
int ny = q[f].dy + d[i][1];
// 判断新坐标是否在地图范围内，且未被访问过，并且不是障碍物（'#'）
if (nx >= 0 && nx < n && ny >= 0 && ny < m && b[nx][ny] == 0 && a[nx][ny] != '#') {
// 将新点加入队列，尾指针后移
r++;
// 标记新点已经被访问过
b[nx][ny] = 1;
// 将新点的坐标存入队列
q[r].dx = nx;
q[r].dy = ny;
// 记录新点到起点的步数
c[nx][ny] = s;
}
}
}
}
int main() {
// 当成功读取到地图的行数n和列数m时，进入循环
while (scanf("%d %d", &n, &m) == 2) {
// 读取地图的每一行信息
for (int i = 0; i < n; i++) {
scanf("%s", a[i]);
}
// 遍历地图，找到起点（Y）和终点（M）的坐标
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 如果当前位置是起点（Y），记录其坐标
if (a[i][j] == 'Y') x1 = i, y1 = j;
// 如果当前位置是终点（M），记录其坐标
else if (a[i][j] == 'M') x2 = i, y2 = j;
}
}
// 定义两个二维数组c1和c2，分别用于记录从起点和终点到各个位置的步数，初始化为0
int c1[203][203] = {0}, c2[203][203] = {0};
// 重置访问标记数组b，将所有位置标记为未访问
memset(b, 0, sizeof(b));
// 从起点开始进行广度优先搜索，记录起点到各个位置的步数
bfs(x1, y1, c1);
// 再次重置访问标记数组b
memset(b, 0, sizeof(b));
// 从终点开始进行广度优先搜索，记录终点到各个位置的步数
bfs(x2, y2, c2);
// 初始化最小步数为一个较大的值
int min = 100000;
// 遍历地图，找到所有目标点（'@'），并计算从起点和终点到该点的步数之和
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 如果当前位置是目标点（'@'），并且当前步数之和小于最小步数，且步数之和不为0
if (a[i][j] == '@' && (min > c1[i][j] + c2[i][j]) && (c1[i][j] + c2[i][j])) {//标记那处非常关键
// 更新最小步数
min = c1[i][j] + c2[i][j];
}
}
}
// 输出最小步数乘以11的结果
printf("%d\n", min * 11);
}
return 0;
}
#include<stdio.h>
int n,k,a[25]={0},cnt=0;
int p(int num){
int z=1;
if(num<2)z=0;
for(int i=2;i*i<=num;i++){
if(num%i==0){
z=0;
break;
}
}
return z;
}
void dfs(int f,int num,int sum){
if(num==0){
if(p(sum))cnt++;
return ;
}
if(n-f+1<num)return;
for(int i=f;i<=n;i++){
dfs(i+1,num-1,sum+a[i]);
}
}
int main()
{
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
dfs(1,k,0);
printf("%d\n",cnt);
return 0;
}
今天在洛谷练了几道搜索题，无习巩固了队列和站的相关知识点，回顾了一下归并算法和快速排序法