中国海洋大学第四届朗讯杯高级组 A Rocky

http://acm.sdut.edu.cn/sdutoj/showproblem.php?pid=2718&cid=1203

题意:给你一个m乘n的格子阵,从一边进去,直线往前走,如果前边有石头就往右走,如果右边还有石头就往左走,如果左边还有石头就忘回走,会给你一个起始点的坐标,当然是在4条边上,但是不会在角上,问你在哪个格子走出去,且走了多少步。

思路:DFS。好吧,当时做的时候卡在这儿,一直没D出来。。。。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
int map[maxn][maxn]; int step=,n,m;
void dfs(int x,int y,int flag)
{
if(flag == )//右
{
bool flag1 = false;
for(int i = x ; i <= n ; i++)
{
if(map[i][y])//一直走直到前边是石头为止
{
flag1 = true ;
step += (i-x-);//把前边走过的都加上但要减去当前占的这个格子,所以减1
if(!map[i-][y-])//如果右边没有石头向右转
{
dfs(i-,y,);//右的右边是下
break;//结束掉每一次的循环,因为有石头之后循环就不应该进行了
}
else if(map[i-][y-]&&!map[i-][y+])//向上
{
dfs(i-,y,);
break;
}
else if(map[i-][y-]&&map[i-][y+])//回去
{
dfs(i-,y,);
break;
}
}
}
if(!flag1)
{
step += (n-x);
printf("%d %d %d\n",n,y,step);
return;
}
}
else if(flag == )//上
{
bool flag2=false;
for(int i = y ; i <= m ; i++)
{
if(map[x][i])
{
flag2 = true ;
step += (i-y-) ;
if(!map[x+][i-])
{
dfs(x,i-,);
break;
}
else if(map[x+][i-]&&!map[x-][i-])
{
dfs(x,i-,);
break;
}
else if(map[x+][i-]&&map[x-][i-])
{
dfs(x,i-,);
break;
}
}
}
if(!flag2)
{
step += (m-y);
printf("%d %d %d\n",x,m,step);
}
}
else if(flag == )//左
{
bool flag3 = false;
for(int i = x ; i >= ; i--)
{
if(map[i][y])
{
flag3 = true ;
step += (x-i-);
if(!map[i+][y+])
{
dfs(i+,y,);
break;
}
else if(map[i+][y+]&&!map[i+][y-])
{
dfs(i+,y,);
break;
}
else if(map[i+][y+]&&map[i+][y-])
{
dfs(i+,y,);
break;
}
}
}
if(!flag3)
{
step += x-;
printf("%d %d %d\n",,y,step);
}
}
else if(flag == )//下
{
bool flag4 = false;
for(int i = y ; i >= ; i--)
{
if(map[x][i])
{
flag4 = true;
step += (y-i-);
if(!map[x-][i+])
{
dfs(x,i+,);
break;
}
else if(map[x-][i+]&&!map[x+][i+])
{
dfs(x,i+,);
break;
}
else if(map[x-][i+]&&map[x+][i+])
{
dfs(x,i+,);
break;
}
}
}
if(!flag4)
{
step += y-;
printf("%d %d %d\n",x,,step);
}
}
} int main()
{
int k,sx,sy;
int cnt = ;
while(scanf("%d%d%d",&n,&m,&k)!=EOF)
{
if(n==&&m==&&k==) break;
step = ;//初始格子算一步
memset(map,,sizeof(map));
for(int i = ; i < k ; i++)
{
int x,y;
scanf("%d%d",&x,&y);
map[x][y] = ;//将这些点标记为1代表不能走
}
int flag;
scanf("%d %d",&sx,&sy);
if(sx == ) flag = ;//右
else if(sy == ) flag = ;//上
else if(sy == m) flag = ;//下
else if(sx == n) flag = ;//左
printf("Case %d: ",cnt);
cnt++;
dfs(sx,sy,flag);
}
return ;
}
上一篇:安装最新版本的ReSharper导致原生全局搜索工具的消失问题


下一篇:oracle group by rollup,decode,grouping,nvl,nvl2,nullif,grouping_id,group_id,grouping sets,RATIO_TO