#2
九转星河2017-07-25 14:47
|
程序代码:
/*此代码所要解决的问题:
输入有三部分 第一行 有两个数字分别代表下面几行(除了最后一行)的行数和列数 最后一行代表的是 公主的位置(坐标) 中间的几行有"#"和"O"他们分别代表的意思是 "#"中间是一个屋子四面都是墙 "O"的意思是
四面都是空的(没有墙) 王子手里的宝剑 在三个单位时间内 可以 打破一堵墙 王子从一个房间 跨越到另一个房间需要 1个单位时间 (王子只能 在上下左右 这四个方向上移动 ) 现在给你 上述信息 你需要求出来王子 在用时 最短的情况下 几分钟可以将 公主解救出来 .*/
#include <stdio.h>
#include <string.h>
int min=1000000,a,b,visit[55][55];//拯救者
char maze[55][55];//迷宫坐标
int main()
{
int i,j,m,n;
while(scanf("%d%d%*c",&a,&b)==2)
{
for(i=1;i<=a;i++){
for(j=1;j<=b;j++)
scanf("%c",&maze[i][j]);
getchar();
}
scanf("%d%d",&m,&n);
memset(visit,0,sizeof(visit));
visit[1][1]=1;
dfs(1,1,m,n,0);
printf("%d\n",min);
}
return 0;
}
void dfs(int x,int y,int m,int n,int sum)
{
if(x==m&&y==n)
{
if(sum<min)
min=sum;
}
else{
if(x-1>0&&(!visit[x-1][y]))
{
visit[x-1][y]=1;
if(maze[x-1][y]=='#') dfs(x-1,y,m,n,sum+4);
else dfs(x-1,y,m,n,sum+1);
visit[x-1][y]=0;
}
if(x+1<=a&&(!visit[x+1][y]))
{
visit[x+1][y]=1;
if(maze[x+1][y]=='#') dfs(x+1,y,m,n,sum+4);
else dfs(x+1,y,m,n,sum+1);
visit[x+1][y]=0;
}
if(y-1>0&&(!visit[x][y-1]))
{
visit[x][y-1]=1;
if(maze[x][y-1]=='#') dfs(x,y-1,m,n,sum+4);
else dfs(x,y-1,m,n,sum+1);
visit[x][y-1]=0;
}
if(y+1<=b&&(!visit[x][y+1]))
{
visit[x][y+1]=1;
if(maze[x][y+1]=='#') dfs(x,y+1,m,n,sum+4);
else dfs(x,y+1,m,n,sum+1);
visit[x][y+1]=0;
}
}
}
输入有三部分 第一行 有两个数字分别代表下面几行(除了最后一行)的行数和列数 最后一行代表的是 公主的位置(坐标) 中间的几行有"#"和"O"他们分别代表的意思是 "#"中间是一个屋子四面都是墙 "O"的意思是
四面都是空的(没有墙) 王子手里的宝剑 在三个单位时间内 可以 打破一堵墙 王子从一个房间 跨越到另一个房间需要 1个单位时间 (王子只能 在上下左右 这四个方向上移动 ) 现在给你 上述信息 你需要求出来王子 在用时 最短的情况下 几分钟可以将 公主解救出来 .*/
#include <stdio.h>
#include <string.h>
int min=1000000,a,b,visit[55][55];//拯救者
char maze[55][55];//迷宫坐标
int main()
{
int i,j,m,n;
while(scanf("%d%d%*c",&a,&b)==2)
{
for(i=1;i<=a;i++){
for(j=1;j<=b;j++)
scanf("%c",&maze[i][j]);
getchar();
}
scanf("%d%d",&m,&n);
memset(visit,0,sizeof(visit));
visit[1][1]=1;
dfs(1,1,m,n,0);
printf("%d\n",min);
}
return 0;
}
void dfs(int x,int y,int m,int n,int sum)
{
if(x==m&&y==n)
{
if(sum<min)
min=sum;
}
else{
if(x-1>0&&(!visit[x-1][y]))
{
visit[x-1][y]=1;
if(maze[x-1][y]=='#') dfs(x-1,y,m,n,sum+4);
else dfs(x-1,y,m,n,sum+1);
visit[x-1][y]=0;
}
if(x+1<=a&&(!visit[x+1][y]))
{
visit[x+1][y]=1;
if(maze[x+1][y]=='#') dfs(x+1,y,m,n,sum+4);
else dfs(x+1,y,m,n,sum+1);
visit[x+1][y]=0;
}
if(y-1>0&&(!visit[x][y-1]))
{
visit[x][y-1]=1;
if(maze[x][y-1]=='#') dfs(x,y-1,m,n,sum+4);
else dfs(x,y-1,m,n,sum+1);
visit[x][y-1]=0;
}
if(y+1<=b&&(!visit[x][y+1]))
{
visit[x][y+1]=1;
if(maze[x][y+1]=='#') dfs(x,y+1,m,n,sum+4);
else dfs(x,y+1,m,n,sum+1);
visit[x][y+1]=0;
}
}
}
[此贴子已经被作者于2017-7-25 10:51编辑过]