AcWing 1097. 池塘计数
flood fill问题：一般来说都是先变换当前点，然后再dfs周围点
int n,m;
const int N = 1000,M=1000;
char map[N][M];
int dx[8] = {1,0,1,1,-1,-1,0,-1};
int dy[8] = {0,1,1,-1,1,-1,-1,0};
void dfs(int x,int y){
for(int i=0;i<8;i++){
if(x+dx[i]>=0&&x+dx[i]<n&&y+dy[i]>=0&&y+dy[i]<m&&map[x+dx[i]][y+dy[i]]=='W'){
map[x+dx[i]][y+dy[i]]='.';
dfs(x+dx[i],y+dy[i]);
}
}
}
int main(int argc, char** argv) {
cin>>n>>m;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
char temp;
cin>>temp;
map[i][j] = temp;
}
}
int res = 0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(map[i][j]=='W'){
res++;
dfs(i,j);
}
}
}
printf("%d",res);
}
- 城堡问题
int n,m;
const int N = 52,M=52;
int m1[N][M],m2[N][M],m3[N][M],m4[N][M],map[N][M];
//南东北西
//注意墙为0才是通过
void dfs(int x,int y,int& tempmax){
//printf("dfs: (%d, %d)\n",x+1,y+1);
tempmax++;
if(m1[x][y]==0&&x+1<n&&map[x+1][y]==0){
map[x+1][y]=1;
dfs(x+1,y,tempmax);
}
if(m2[x][y]==0&&y+1<m&&map[x][y+1]==0){
map[x][y+1]=1;
dfs(x,y+1,tempmax);
}
if(m3[x][y]==0&&x-1>=0&&map[x-1][y]==0){
map[x-1][y]=1;
dfs(x-1,y,tempmax);
}
if(m4[x][y]==0&&y-1>=0&&map[x][y-1]==0){
map[x][y-1]=1;
dfs(x,y-1,tempmax);
}
}
int main(int argc, char** argv) {
cin>>n>>m;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
int temp;
cin>>temp;
if(temp/8==1){
m1[i][j]=1;
temp-=8;
}
if(temp/4==1){
m2[i][j]=1;
temp-=4;
}
if(temp/2==1){
m3[i][j]=1;
temp-=2;
}
if(temp==1){
m4[i][j]=1;
}
}
}
int res = 0;
int t_max = 0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(map[i][j]==0){
//printf("new room:(%d, %d)\n",i+1,j+1);
int tempmax = 0;
map[i][j] = 1;
res++;
dfs(i,j,tempmax);
if(tempmax>t_max)t_max = tempmax;
}
}
}
printf("%d\n%d",res,t_max);
}
- 迷宫问题
经典bfs：利用队列模拟
int n;
typedef pair<int,int> PII;
const int N = 1010;
int m[N][N];
PII path[N][N];
int dx[4]={0,-1,0,1},dy[4] = {1,0,-1,0};
void bfs(){
queue<PII> q;
PII n1,n2;
q.push(make_pair(n-1,n-1));
while(q.size()){
n1 = q.front();
q.pop();
for(int i=0;i<4;i++){
n2 = make_pair(n1.first+dx[i],n1.second+dy[i]);
if(n2.first>=0&&n2.first<n&&n2.second>=0&&n2.second<n&&m[n2.first][n2.second]==0){
path[n2.first][n2.second] = n1;
m[n2.first][n2.second] = 1;
q.push(n2);
}
}
}
}
int main(int argc, char** argv) {
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>m[i][j];
}
}
bfs();
PII temp = make_pair(0,0);
while(temp.first!=n-1||temp.second!=n-1){
printf("%d %d\n",temp.first,temp.second);
temp = path[temp.first][temp.second];
}
printf("%d %d\n",n-1,n-1);
}
- 武士风度的牛
int n,m;
typedef pair<int,int> PII;
const int N = 1010;
int hx,hy;
int kx,ky;
char map[N][N];
int plen[N][N];
int dx[8]={-1,-2,-2,-1,1,2,2,1};
int dy[8]={2,1,-1,-2,-2,-1,1,2};
void bfs(){
queue<PII> q;
PII n1,n2;
q.push(make_pair(hx,hy));
while(q.size()){
if(plen[kx][ky])break;
n1 = q.front();
q.pop();
for(int i=0;i<8;i++){
n2 = make_pair(n1.first+dx[i],n1.second+dy[i]);
if(n2.first>=0&&n2.first<n&&n2.second>=0&&n2.second<m&&map[n2.first][n2.second]!='*'){
plen[n2.first][n2.second] = plen[n1.first][n1.second]+1;
map[n2.first][n2.second] = '*';
q.push(n2);
}
}
}
}
int main(int argc, char** argv) {
cin>>m>>n;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>map[i][j];
if(map[i][j]=='H'){
hx=i;hy=j;
}
if(map[i][j]=='K'){
kx=i;ky=j;
}
}
}
bfs();
printf("%d",plen[kx][ky]);
}
AcWing 1100. 抓住那头牛
虽然过了但是还是有很多疑惑：
1、数组开的大小，因为可能会需要记录很大的数有没有搜索过，开一个仅比n、k大的数组其实不对
2、如何优化搜索
看了题解：
如果是奇数目标，最后一步肯定是+1或-1
总之就是不断讨论各个操作发生在最优情况的可能性
int n,k;
typedef pair<int,int> PII;
int map[100010];
int main(int argc, char** argv) {
cin>>n>>k;
//cout<<endl;
queue<PII> q;
q.push(make_pair(k,0));
while(q.size()){
PII temp = q.front();
//cout<<temp.first<<" "<<temp.second<<endl;
q.pop();
if(temp.first==n){
cout<<temp.second;
return 0;
}
if(map[temp.first-1]==0){
q.push(make_pair(temp.first-1,temp.second+1));
map[temp.first-1]=1;
}
if(map[temp.first+1]==0){
q.push(make_pair(temp.first+1,temp.second+1));
map[temp.first+1]=1;
}
if(temp.first%2==0&&map[temp.first/2]==0){
q.push(make_pair(temp.first/2,temp.second+1));
map[temp.first/2]=1;
}
}
}
头文件及声明
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#include <string>
using namespace std;
