算法
这两天对搜索(主要是dfs)进行了复习,写了四道题目.
解题思路
这道题我用dfs进行解题,这道题比起其他的只多了一个Z轴也就是多了两个方向.
代码
#include <string.h>
#include <stdio.h>
char g[31][31][31];
int ne[7][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
int j[31][31][31];
struct dui
{
int x;
int y;
int z;
}d[31*31*31];
int l,r;
int x,y,z;
int bfs()
{
int tx,ty,tz,k;
while(l<r)
{
for(k=0;k<6;k++)
{
tz=ne[k][0]+d[l].z;
tx=ne[k][1]+d[l].x;
ty=ne[k][2]+d[l].y;
if(tz>z||tz<0||tx>x||tx<0||ty>y||ty<0)
continue;
if(g[tz][tx][ty]=='E')
{
return j[d[l].z][d[l].x][d[l].y]+1;
}
if(j[tz][tx][ty]==0&&g[tz][tx][ty]=='.')
{
j[tz][tx][ty]=j[d[l].z][d[l].x][d[l].y]+1;
d[r].z=tz;
d[r].x=tx;
d[r++].y=ty;
}
}
l++;
}
return 0;
}
int main()
{
int a,b,c;
while(1)
{
scanf("%d%d%d",&z,&x,&y);
if(x==0&&y==0&&z==0)
break;
l=0;
r=0;
memset(j,0,sizeof(int)*31*31*31);
for(c=0;c<z;c++)
{
for(a=0;a<x;a++)
{
scanf("%s",g[c][a]);
}
}
for(c=0;c<z;c++)
{
for(a=0;a<x;a++)
{
for(b=0;b<y;b++)
{
if(g[c][a][b]=='S')
{
j[c][a][b]=1;
d[r].z=c;
d[r].x=a;
d[r++].y=b;
int k=bfs();
if(k!=0)
{
printf("Escaped in %d minute(s).\n",k-1);
}
else
{
printf("Trapped!\n");
}
}
}
}
}
}
return 0;
}
解题思路
这道题遍历即可解决,但如果使用纯暴力会超时计算量太大,所以要用二进制遍历.
因为每翻一次周围的也会跟着翻一次,而且如果某一个瓷砖翻两次就相当于没有进行翻动,所以我们可以对第一行进行一个假设.假设第一行每个瓷砖的翻面次数,对第一行进行翻面后如果第一行还有黑色存在那必然是这个瓷砖下面的瓷砖进行了翻面.如果到最后一行进行翻面后还有黑色瓷砖则代表第一行翻面次数不对.
PS:这道题目因为可能有多个答案所以还要考虑比较翻面次数,只取翻面次数最小的.
代码
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
using namespace std;
int g[20][20];
int j[20][20];
int gg[20][20];
int jj[20][20];
int ne[6][2]={{1,0},{-1,0},{0,1},{0,-1},{0,0}};
int h[20];
int n,m;
int k;
int dfs(int i)
{
for(int y=0;y<n;y++)
{
if(j[i][y]==1)
{
for(int x=0;x<5;x++)
{
int tx=i+ne[x][0];
int ty=y+ne[x][1];
if(tx<0||tx>=m||ty<0||ty>=n)
continue;
if(gg[tx][ty]==0)
{
gg[tx][ty]=1;
}
else
{
gg[tx][ty]=0;
}
}
}
}
if(i+1==m)
{
for(int y=0;y<n;y++)
{
if(gg[i][y]==1)
return 0;
}
return 1;
}
for(int y=0;y<n;y++)
{
if(gg[i][y]==1)
{
j[i+1][y]=1;
}
}
return dfs(i+1);
}
void cls()
{
for(int x=0;x<m;x++)
{
for(int y=0;y<n;y++)
{
gg[x][y]=g[x][y];
}
}
memset(j,0,sizeof(int )*20*20);
}
int main()
{
int x,y,mi=999999;
scanf("%d%d",&m,&n);
for(x=0;x<m;x++)
{
for(y=0;y<n;y++)
{
scanf("%d",&g[x][y]);
}
}
for(x=0;x<1<<n;x++)
{
k=0;
cls();
for(y=0;y<n;y++)
{
j[0][y]=h[y];
}
k=dfs(0);
if(k!=0)
{
k=0;
for(int l=0;l<m;l++)
{
for(int r=0;r<n;r++)
{
if(j[l][r]==1)
k++;
}
}
if(k<mi)
{
mi=k;
for(int l=0;l<m;l++)
{
for(int r=0;r<n;r++)
{
jj[l][r]=j[l][r];
}
}
}
}
int d=n-1;
h[d]+=1;
while(h[d]==2)
{
h[d]=0;
d--;
h[d]++;
}
}
if(mi==999999)
{
printf("IMPOSSIBLE");
}
else
{
for(x=0;x<m;x++)
{
for(y=0;y<n;y++)
{
printf("%d ",jj[x][y]);
}
printf("\n");
}
}
return 0;
}
解题思路
简单的dfs就可以解决,我们只要每遇到石油就将与它相邻的石油打上标记就好.
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
using namespace std;
char g[110][110];
int ne[9][2]={{1,0},{-1,0},{0,1},{0,-1},{-1,-1},{1,-1},{-1,1},{1,1}};
int n,m;
int dfs(int x,int y)
{
int tx,ty,z;
for(z=0;z<8;z++)
{
tx=ne[z][0]+x;
ty=ne[z][1]+y;
if(tx<0||tx>m||ty<0||ty>n)
continue;
if(g[tx][ty]=='@')
{
g[tx][ty]='*';
dfs(tx,ty);
}
}
return 0;
}
int main()
{
int sum=0;
while(1)
{
sum=0;
scanf("%d%d",&m,&n);
//getchar();
if(n==0&&m==0)
break;
for(int x=0;x<m;x++)
{
scanf("%s",g[x]);
//getchar();
}
for(int x=0;x<m;x++)
{
for(int y=0;y<n;y++)
{
if(g[x][y]=='@')
{
g[x][y]='*';
dfs(x,y);
sum++;
}
}
}
printf("%d\n",sum);
}
return 0;
}
java
我初步了解了java的基本语法,基本的数据类型和数组的定义与运用.
