第二周培训

dfs深度优先搜索
https://www.luogu.com.cn/problem/P8662

`

include<bits/stdc++.h>
using namespace std;
int n;
const int N=1010;
char a[N][N];
int sum,ans,cnt;
int d[4][2]={0,1,0,-1,1,0,-1,0};
bool f1;
void dfs(int x,int y) {
if (f1 == false) {
cnt = 0;
for (int i = 0; i < 4; i++) {
int x1 = x + d[i][0];
int y1 = y + d[i][1];
if (a[x1][y1] != '.') {
cnt++;
}
}
if (cnt == 4) {
ans++;
f1 = true;
}
}
a[x][y] = '*';
for (int i = 0; i < 4; i++) {
int x2 = x + d[i][0];
int y2 = y + d[i][1];
if (a[x2][y2] == '#' && x2 >= 0 && x2 < n && y2 >= 0 && y2 < n) {
dfs(x2, y2);
}
}
}
int main(){
cin >> n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin >> a[i][j];
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++) {
if (a[i][j] == '#') {
sum++;
f1 = false;
dfs(i, j);
}
}
}
cout << sum-ans << endl;
return 0;
}

`

strlen()
https://www.luogu.com.cn/problem/P1914

`

include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
char str[100];
cin >> str;
int len=strlen(str);
for(int i=0;i<len;i++){
str[i]=(str[i]-'a'+n)%26+'a';
cout << str[i] ;
}
cout << endl;
return 0;
}

`
计算一个char类型字符数组的长度可以使用 int len=strlen(chat);

map

`

include<bits/stdc++.h>
using namespace std;
int n;
map<int,int>mp;
int main(){
cin >> n;
vectorv(n);
for(int i=0;i<n;i++){
cin >> v[i];
mp[v[i]]++;
}
int count=0;
for(int i=0;i<n;i++){
v[i]+=9;
mp[v[i]]++;
if(mp[v[i]]!=1) count++;
}
cout << n-count;
return 0;
}
`
map是C++STL的一个容器，提供一对一的映射关系
第一个称为关键字“key”，别名是first
第二个称为关键字的价值“value”，别名是second
map<int,int>mp;
map<string,string>mp;
map<char,int>mp;
map<int,string>mp;
map<float,int>mp;
map<double,long>mp;
map<person,int>mp;

map使用：
1.
map<char,int>mp; mp.insert('a',1); mp.insert('b',1); mp['a']++; mp['c']++;
2.插入元素
map<int,string>mp; 方式一：用insert函数插入一个pair mp.insert(pair<int,string>(0,"zhangsan")); 方式二：用insert函数插入value_type数据 mp.insert(map<int,string>::value_type(1,"lisi")); 方式三：用类似数组的方式增加元素（！！！key是int或类似int；不等于数组，key可以为负数） mp[123]="wangwu";
3.查找元素
find（）返回一个迭代器，指向查找的元素，找不到则返回map::end()位置(NULL)
`
intr=mp.find(123);
if(iter!=mp.end())
cout << "found,the value is" << iter->second;
else
cout << "not found";

如果关键字是整型，也可以通过名片[1]读取关键字1对应的价值
`

4。几种引用方法
`
1）
map<int,int>mp1;
int sum=0;
mp1[10]=3;
sum+=mp1[10];
\sum累加后变为103

2）
map<int,int>mp1;
int sum=100;
sum+=mp1[10];
\mp1不存在key为10，所以mp1返回值为0，sum累加后仍为100

3）
map<int,int>mp1;
mp1[10]=3;
mp1[10]++;
\mp1[10]变为4

map<int,int>mp1;
mp1[20[++;
\mp1增加一个元素<20,1>

`