目录
201. 部分和问题【爆搜】
https://www.papamelon.com/problem/201
#include<bits/stdc++.h>
using namespace std;
const int N=25;
typedef long long int LL;
LL a[N],st[N],n,m,flag;
void dfs(int sum,int k)
{
if(sum==m) flag=1;
if(k==n) return;
dfs(sum+a[k],k+1);
dfs(sum,k+1);
}
int main(void)
{
while(cin>>n)
{
flag=0;
for(int i=0;i<n;i++) cin>>a[i];
cin>>m;
dfs(0,0);
if(flag) puts("Yes");
else puts("No");
}
return 0;
}
202. 水洼计数 Lake Counting【连通块】
https://www.papamelon.com/problem/202
#include<bits/stdc++.h>
using namespace std;
const int N=110;
string s[N];
int st[N][N],n,m,cnt;
int dx[8]={-1,-1,-1,0,0,1,1,1};
int dy[8]={-1,0,1,-1,1,-1,0,1};
void dfs(int x,int y)
{
st[x][y]++;
for(int i=0;i<8;i++)
{
int tempx=x+dx[i];
int tempy=y+dy[i];
if(tempx<0||tempx>=n||tempy<0||tempy>=m) continue;
if(st[tempx][tempy]) continue;
if(s[tempx][tempy]!='W') continue;
dfs(tempx,tempy);
}
}
int main(void)
{
cin>>n>>m;
for(int i=0;i<n;i++) cin>>s[i];
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(!st[i][j]&&s[i][j]=='W')
{
dfs(i,j);
cnt++;
}
}
}
cout<<cnt<<endl;
return 0;
}
203. 迷宫的最短路径【bfs】
https://www.papamelon.com/problem/203
#include<bits/stdc++.h>
using namespace std;
const int N=110;
string s[N];
int st[N][N],n,m;
int stx,sty,edx,edy;
struct node{int x,y,step;};
int dx[4]={-1,0,0,1};
int dy[4]={0,-1,1,0};
int bfs(int x,int y)
{
queue<node>q; q.push({x,y,0});
st[x][y]=1;
while(q.size())
{
auto temp=q.front(); q.pop();
x=temp.x,y=temp.y;
int d=temp.step;
if(x==edx&&y==edy) return d;
for(int i=0;i<4;i++)
{
int tempx=x+dx[i];
int tempy=y+dy[i];
if(tempx<0||tempx>=n||tempy<0||tempy>=m) continue;
if(st[tempx][tempy]) continue;
if(s[tempx][tempy]=='#') continue;
q.push({tempx,tempy,d+1});
st[tempx][tempy]=1;
}
}
return -1;
}
int main(void)
{
cin>>n>>m;
for(int i=0;i<n;i++) cin>>s[i];
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(s[i][j]=='S') stx=i,sty=j;
if(s[i][j]=='G') edx=i,edy=j;
}
}
cout<<bfs(stx,sty);
return 0;
}