【每日一题C】#80. 小明看电影

た入场券 2023-10-11 17:25 10阅读 0赞

![55607eca93df4366824d6f7681e15f84.png][]

![32fb921b70e141e78d2f93bdab88d4c5.png][]

**题目摘述：**

因为市政大力修路和挖地铁，有些到电影院的道路不允许步行，请判断小明能否从学校走到电影院（只能朝上下左右四个方向行走），如果能到，则输出最短步数，如果不能到，则输出 No。

**初始代码**：

#include<stdio.h>
    #include<string.h>
    int n,m,p,q,min=250000,key=0;//key判断是否可达 
    char a[501][501],book[501][501];//a记录道路情况,book用来记录走过的块 
    void DFS(int x,int y,int step)
    {
    	int next[4][2] = {
       {0,1},{1,0},{0,-1},{-1,0}};
    	int tx,ty,k;
    	if(x == p&&y == q)
    	{
    		if(step<min) min = step;
    		key=1; 
    		return ;
    	}
    	for(k = 0;k <= 3;k++)//下一步，右、下、左、上
    	{
    		tx = x + next[k][0];
    		ty = y + next[k][1];
    		if(tx<1||tx>n||ty<1||ty>m) continue;//越界
    		if(a[tx][ty]=='.'&& book[tx][ty]=='.'||a[tx][ty]=='g')
    		{
    			book[tx][ty] = '#';//记录已走该步
    			DFS(tx,ty,step+1);//递归，从当前步继续查找所有可行块
    			book[tx][ty] = '.';//下一步走投无路，则退出该步
    		}
    	}
    	return;
     } 
     
     int main()
     {
     	int i,j,startx,starty;
     	scanf("%d%d",&n,&m); 	
     	for(i = 1;i<=n;i++)
     	{
     		char s[500];
    		scanf("%s",s);
     		for(j = 1;j<=m;j++)	{	
     		book[i][j]='.'; //初始未行，book用来记录走过的块，所有都为.
     		a[i][j]=s[j-1];//a记录道路情况
    		if(a[i][j]=='s'){
    			startx=i;
    			starty=j;
    		}
    		if(a[i][j]=='g'){
    			p=i;
    			q=j;
    		}
    		}
    	 }
    	book[startx][starty] = '#';//不可行块
    	DFS(startx,starty,0);
    	if(key) 
    		printf("%d\n",min);
    	else
    		printf("No\n");
    	return 0;
     }

**输出结果举例**：

5 5
    #s###
    ...##
    .##..
    .#...
    ...#g
    11

**运行情况提示超时，代码应再进一步优化**：

![25c55cc73a0d40b7b706e022e55c2964.png][]

明天再接着学习如何优化吧。

**参考链接**：

1、[http://t.csdn.cn/0KCgv][http_t.csdn.cn_0KCgv]

2、[http://t.csdn.cn/5DDCe][http_t.csdn.cn_5DDCe]

[55607eca93df4366824d6f7681e15f84.png]: https://img-blog.csdnimg.cn/55607eca93df4366824d6f7681e15f84.png
[32fb921b70e141e78d2f93bdab88d4c5.png]: https://img-blog.csdnimg.cn/32fb921b70e141e78d2f93bdab88d4c5.png
[25c55cc73a0d40b7b706e022e55c2964.png]: https://img-blog.csdnimg.cn/25c55cc73a0d40b7b706e022e55c2964.png
[http_t.csdn.cn_0KCgv]: http://t.csdn.cn/0KCgv
[http_t.csdn.cn_5DDCe]: http://t.csdn.cn/5DDCe