简单水池&&迷宫问题

#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;
int M[101][101],flag[101][101];
int n,m;
int cnt;
void pool(int x,int y)
{
flag[x][y]=1;
M[x][y]=cnt;
if(x-1>=1&&M[x-1][y]!=0&&flag[x-1][y]==0) pool(x-1,y);
if(x+1<=n&&M[x+1][y]!=0&&flag[x+1][y]==0) pool(x+1,y);
if(y-1>=1&&M[x][y-1]!=0&&flag[x][y-1]==0) pool(x,y-1);
if(y+1<=m&&M[x][y+1]!=0&&flag[x][y+1]==0) pool(x,y+1);
}
int main()
{
int i,j,t;
cin>>t;
while(cin>>n>>m&&t--)
{
cnt=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
cin>>M[i][j];
//cout<<endl; // memset(m,0,sizeof(m));
memset(flag,0,sizeof(flag));
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(M[i][j]==1&&flag[i][j]==0)
{
cnt++;pool(i,j);
}
printf("%d\n",cnt);
// for(i=1;i<=n;cout<<endl,i++)
// for(j=1;j<=m;j++)
// cout<<M[i][j]<<" ";
}
return 0;
}
//这一道题是有关搜索的,看看就行
#include <iostream>
#include <cstring>
using namespace std;
int a,b,c,d,sum,cnt;
int M[9][9]={
{1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,1,0,1},
{1,0,0,1,1,0,0,0,1},
{1,0,1,0,1,1,0,1,1},
{1,0,0,0,0,1,0,0,1},
{1,1,0,1,0,1,0,0,1},
{1,1,0,1,0,1,0,0,1},
{1,1,0,1,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1}};
void dfs(int x,int y,int cnt)
{
if(x==c&&y==d) {if(cnt<sum) sum=cnt;}
else{
if(!M[x-1][y]) {M[x-1][y]=1; dfs(x-1,y,cnt+1); M[x-1][y]=0;}
if(!M[x+1][y]) {M[x+1][y]=1; dfs(x+1,y,cnt+1); M[x+1][y]=0;}
if(!M[x][y-1]) {M[x][y-1]=1; dfs(x,y-1,cnt+1); M[x][y-1]=0;}
if(!M[x][y+1]) {M[x][y+1]=1; dfs(x,y+1,cnt+1); M[x][y+1]=0;}
}
}
int main()
{
int t;
cin>>t;
while(t--&&cin>>a>>b>>c>>d)
{
cnt=0,sum=81;
dfs(a,b,cnt);
cout<<sum<<endl;
}
return 0;
}

这道题的代码,一开始不是这样写的,我另外定义一个flag,把每次访问的都标记,不过后面觉得这个是多此一举,可以在原来的数组上面,每次访问过后,都标记为墙1,这样就ok了,还有一个就是求最小的值,这个在dfs函数里面开始就给一个判断,其实大概的思路就是先找到一条路,记下步数,然后每次回溯,还原被标记的点,这样继续求出其他路径的值。。。。

#include <iostream>
#include <cstring>
using namespace std;
int M[9][9]={
{1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,1,0,1},
{1,0,0,1,1,0,0,0,1},
{1,0,1,0,1,1,0,1,1},
{1,0,0,0,0,1,0,0,1},
{1,1,0,1,0,1,0,0,1},
{1,1,0,1,0,1,0,0,1},
{1,1,0,1,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1}},flag[100][100];
int n,m,cnt=0;
int a,b,c,d;
void maze(int x,int y)
{
if(x==c&&y==d) return; flag[x][y]=1;
if(x-1>=0&&M[x-1][y]==0&&flag[x-1][y]==0) {cnt++; maze(x-1,y); cnt--;flag[x-1][y]=0;}
if(x+1<=8&&M[x+1][y]==0&&flag[x+1][y]==0) {cnt++; maze(x+1,y); cnt--;flag[x+1][y]=0;}
if(y-1>=0&&M[x][y-1]==0&&flag[x][y-1]==0) {cnt++; maze(x,y-1); cnt--;flag[x][y-1]=0;}
if(y+1<=8&&M[x][y+1]==0&&flag[x][y+1]==0) {cnt++; maze(x,y+1); cnt--;flag[x][y+1]=0;}
}
int main()
{
//int i,j;
cin>>a>>b>>c>>d;
memset(flag,0,sizeof(flag));
//for(i=a;i<=8;i++)
// for(j=b;j<=8;j++)
maze(a,b);
cout<<cnt<<endl;
return 0;
}

后面想把路径打印出来,可是出不来,代码如下

#include <iostream>
#include <cstring>
using namespace std;
int a,b,c,d,sum,cnt,LJ1[1000],LJ2[1000],h,k;
int M[9][9]={
{1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,1,0,1},
{1,0,0,1,1,0,0,0,1},
{1,0,1,0,1,1,0,1,1},
{1,0,0,0,0,1,0,0,1},
{1,1,0,1,0,1,0,0,1},
{1,1,0,1,0,1,0,0,1},
{1,1,0,1,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1}};
void dfs(int x,int y,int cnt)
{
LJ1[k++]=x;LJ2[h++]=y;
if(x==c&&y==d) {if(cnt<sum) sum=cnt;}
else{
if(!M[x-1][y]) {M[x-1][y]=1; dfs(x-1,y,cnt+1); M[x-1][y]=0;LJ1[k-1]=0;LJ2[h-1]=0;}
if(!M[x+1][y]) {M[x+1][y]=1; dfs(x+1,y,cnt+1); M[x+1][y]=0;LJ1[k-1]=0;LJ2[h-1]=0;}
if(!M[x][y-1]) {M[x][y-1]=1; dfs(x,y-1,cnt+1); M[x][y-1]=0;LJ1[k-1]=0;LJ2[h-1]=0;}
if(!M[x][y+1]) {M[x][y+1]=1; dfs(x,y+1,cnt+1); M[x][y+1]=0;LJ1[k-1]=0;LJ2[h-1]=0;}
}
}
int main()
{
int t,i;
cin>>t;
while(t--&&cin>>a>>b>>c>>d)
{
k=0;h=0;
memset(LJ1,0,sizeof(LJ1));
memset(LJ2,0,sizeof(LJ2));
cnt=0,sum=81;
dfs(a,b,cnt);
cout<<sum<<endl;
for(i=0;i<=100;i++)
cout<<LJ1[i]<<","<<LJ2[i]<<" → ";
}
return 0;
}

//怎么把路径打印出来,感觉如果走一条路不通,就标记为0,可是又有回溯,就感觉全乱了,如果在每次dfs后,干脆数组全为0,k,h也从0开始应该可以。。。

#include <iostream>
#include <mem.h>
using namespace std;
char M[30][30];
bool Find;
int flag[30][30];
int n,m;
void ss(int x,int y)
{
if(Find==true) return ; cout<<x<<" "<<y<<" →"; flag[x][y]=1;
int a,b;
int i;
//上走
a=x-1;
b=y;
if(a>=1&&M[a][b]!='w'&&flag[a][b]==0)
{
if(M[a][b]=='T')
{
Find=true;
return ;
}
ss(a,b);
}
//下走
a=x+1;
b=y;
//cout<<a<<n<<endl;
if(a<=n&&M[a][b]!='w'&&flag[a][b]==0)
{
if(M[a][b]=='T')
{
Find=true;
return ;
}
ss(a,b);
}
//左走
a=x;
b=y-1;
if(b>0&&M[a][b]!='w'&&flag[a][b]==0)
{
if(M[a][b]=='T')
{
Find=true;
return ;
}
ss(a,b);
}
//右走
a=x;
b=y+1;
if(b<=m&&M[a][b]!='w'&&flag[a][b]==0)
{
if(M[a][b]=='T')
{
Find=true;
return ;
}
ss(a,b);
}
}
int main()
{
int j,i,x,y;
cin>>n>>m;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
cin>>M[i][j];
if(M[i][j]=='s') {x=i;y=j;}
}
memset(flag,0,sizeof(flag));
ss(x,y);
return 0; }
//一个迷宫的问题,和水池问题是一个题型,不多讲了。。。。
上一篇:双网卡绑定(suse)


下一篇:CSS3常用属性,CSS继承和层叠