hdoj 1312 Red and Black【dfs，回溯】

我不是女神ヾ 2022-08-04 12:35 88阅读 0赞

# Red and Black #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)  
Total Submission(s): 13559    Accepted Submission(s): 8414**

题目大意：输入两个整数n、m，表示地图的尺寸，接下来的m行，每行n个字符，其中 ，@表示当前人站的地方（一个数据中有且只有一个），'\#'表示墙（其实原文说的不是墙，这里就先把它当做墙，反正不能走在这上面），‘.’（圆点）表示路（这个可以行走）；

题目要求我们求出人所能站的地方有多少个？（至少一个，应为每个数据中至少有一个@）【即让我们求与@连成一片的圆点有多少个】。

Sample Input

6 9
    ....#.
    .....#
    ......
    ......
    ......
    ......
    ......
    #@...#
    .#..#.
    11 9
    .#.........
    .#.#######.
    .#.#.....#.
    .#.#.###.#.
    .#.#..@#.#.
    .#.#####.#.
    .#.......#.
    .#########.
    ...........
    11 6
    ..#..#..#..
    ..#..#..#..
    ..#..#..###
    ..#..#..#@.
    ..#..#..#..
    ..#..#..#..
    7 7
    ..#.#..
    ..#.#..
    ###.###
    ...@...
    ###.###
    ..#.#..
    ..#.#..
    0 0

Sample Output

45
    59
    6
    13

思路：因为每个数据中@的位置是不定的,故我们得先找出@在何处，找到后，  
① 我们应当依次查看当前位置的上下左右，（思路中我们按上下左右依次查看），先查看上，若上边是圆点，则将当前位置移到这个原点上，并将圆点改为‘\#’，若上便不是圆点，这继续查看下，左，右。  
②然后再依次查看但前位置的上下左右，  
 ⒈若上下左右没有圆点，则返回①，接着查看 ①剩下的三个方向，

⒉若上下左右存在圆点，依照上下左右的顺序查看（就是说先看上，若上有点，则把但前位置移至上，若无，再查看下，若下有圆点，则把当前位置移至下，若无，再查左.....），(笔者以下为例)把的当前位置移至下，然后重复①②，直至把与@连成一片的圆点都标为‘\#’为止；

【注意，@所在的位置也要记录进去！！！】

>>>>>>>>如有看不大懂的或者有bug，可留言评论，谢谢<<<<<<<<

已Accept代码

#include<stdio.h>
    #include<string.h>
    int n,m,sr,sc,total;
    int dx[]={1,0,0,-1};
    int dy[]={0,1,-1,0};
    char map[22][22];
    
    void dfs(int er,int ec){
    	int i;
    	for(i=0;i<4;i++){					//注意第4、5行的数组，此作用为查看但前位置的四周 
    		int nr=er+dx[i];
    		int nc=ec+dy[i];
    		if(nr>=0&&nr<m&&nc>=0&&nc<=n&&map[nr][nc]=='.'){
    			//(上一行的注释)判断是否越界，是否是圆点 
    			map[nr][nc]='#';			//判断通过，先把这个圆点改为‘#’ 
    			total++;					//再把总数+1
    			dfs(nr,nc);					//然后茶轴当前位置四周 
    		}
    	}
    }
    
    int main(){
    	int i,j;
    	while(scanf("%d%d",&n,&m),n|m){
    		for(i=0;i<m;i++){
    			scanf("%s",map[i]);
    			for(j=0;j<n;j++)
    				if(map[i][j]=='@'){		//查找@的位置，并把它记录下来 
    					sr=i;
    					sc=j;
    				}
    		}
    		total=1;
    		dfs(sr,sc);						//从@所在点向四周开始查找 
    		printf("%d\n",total);
    	}
    	return 0;
    }

以下这种风格是半个月前写的，这次一并献上（注释与上一段代码一致）

#include<cstdio>
    #include<iostream>
    using namespace std;
    int cnt,n,m;
    char a[22][22];
    void fun(int x,int y){
        if(a[x][y]=='#')
            return ;
        if(x<1||x>m||y<1||y>n)
            return ;
        cnt++;
        a[x][y]='#';
        fun(x+1,y);
        fun(x-1,y);
        fun(x,y-1);
        fun(x,y+1);
    }
    int main()
    {
        int i,j,x=1,y=1;
        while(scanf("%d%d",&n,&m),n|m){
            for(i=1;i<=m;i++){
                getchar();
                for(j=1;j<=n;j++){
                    scanf("%c",&a[i][j]);
                    if(a[i][j]=='@')
                    {
                        x=i;
                        y=j;
                    }
                }
            }
            cnt=0;
            fun(x,y);
            printf("%d\n",cnt);
        }
        return 0;
    }