注意事项:
这个程序不用回溯,回溯过于浪费时间。
参考代码:
#include<bits/stdc++.h>
using namespace std;
int w,h,maxx;
bool book[24][24]={};//标记数组
int r[4]={-1,0,1,0},
c[4]={0,1,0,-1};
void dfs(int x,int y)//深搜程序
{
for(int i=0;i<4;i++)
{
int tx=x+r[i],//移动位置
ty=y+c[i];
if(tx>=0 && tx<w && ty>=0 && ty<h && book[tx][ty]==0) //是否符合条件
{
book[tx][ty]=1;//标记该位置已走过
maxx++;//步数加1
dfs(tx,ty);//递归(注意:不回溯)
}
}
}
int main()
{
int x=0,y=0;
while(cin>>h>>w && w!=0 && h!=0)//测试多组数据
{
memset(book,0,sizeof(book));//重置标记数组
for(int i=0;i<w;i++)//输入数据
for(int j=0;j<h;j++)
{
char v;
cin>>v;
if(v=='#')book[i][j]=1;//如果该瓷砖是红色的,直接标记
else if(v=='@')//初始位置
{
x=i;
y=j;
book[i][j]=1;//标记
maxx=1;//步数为1
}
}
dfs(x,y); //调用深搜函数
cout<<maxx<<endl; //输出最大值
}
return 0;
}
0.0分
1 人评分
点我有惊喜!你懂得!浏览:1388 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:665 |
简单编码 (C++代码)浏览:726 |
C语言程序设计教程(第三版)课后习题10.7 (C语言代码)浏览:552 |
P1002 (C语言代码)浏览:1019 |
A+B for Input-Output Practice (C++代码)浏览:631 |
C语言程序设计教程(第三版)课后习题10.5 (C语言代码)浏览:565 |
C语言程序设计教程(第三版)课后习题6.11 (C语言代码)浏览:562 |
wu-淘淘的名单 (C++代码)浏览:1526 |
关于float,double变量的几点说明浏览:1924 |