HDU 1312 Red and Black(dfs)

￡神魔★判官ぃ 2022-08-09 06:16 240阅读 0赞

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1312

一道简单的深搜题目

题意：统计“@”所在区域内，“.”的个数（“@”也被计算在内）

注意题目要求是先输入列的个数，再输入行的个数，坑！

不要忘记标记

code：

#include<stdio.h>
    #include<iostream>
    #include<string>
    #include<string.h>
    using namespace std;
    int vis[50][50];
    string mapp[50];
    int x=0,y=0,i,j,col,row,cnt;
    void dfs(int i,int j)
    {
    	if(mapp[i][j]=='#'||i<0||i>=row||j<0||j>=col||vis[i][j])
    		return ;		
    	cnt++;
    	vis[i][j]=1;
    	dfs(i+1,j);
    	dfs(i,j+1);
    	dfs(i-1,j);
    	dfs(i,j-1);
    }
    int main()
    {
    	while(cin>>col>>row)
    	{
    		if(!col&&!row)
    			break;
    		for(i=0;i<row;i++)
    			cin>>mapp[i];
    		for(i=0;i<row;i++)
    			for(j=0;j<col;j++)
    				if(mapp[i][j]=='@')
    				{
    					x=i;
    					y=j;
    					mapp[i][j]='.';
    					break;
    				}
    		cnt=0;
    		memset(vis,0,sizeof(vis));
    		dfs(x,y);
    		cout<<cnt<<endl;
    	}
    	return 0;
    }

在调试的过程中发现C++中的string类要比char好用一些

而且使用C++的输入语句不需要再考虑scanf后自带的回车

说到scanf后自带的回车，可以加getchar()去除

也可以在输入语句中加一个空格，例如：

for(i=0;i<row;i++)
    		for(j=0;j<col;j++)
    			scanf(" %c",&mapp[i][j]);

额，上面那道题的代码好像有点问题，无法输出结果，但是交杭电可以过，醉了。

下面贴个能输出结果，杭电又能过的代码......     =\_= 汗~

code：

#include<stdio.h>
    #include<string.h>
    #include<string>
    #include<iostream>
    using namespace std;
    int cnt;
    char map[50][50];
    int vis[50][50];
    int i,j,n,m,x=0,y=0;
    void dfs(int i,int j)
    {
        if(map[i][j]=='#'||i<1||i>m||j<1||j>n||vis[i][j])
            return ;
        cnt++;
        vis[i][j]=1;
        dfs(i+1,j);
        dfs(i,j+1);
        dfs(i-1,j);
        dfs(i,j-1);
    }
    int main()
    {
        while(cin>>n>>m)
        {
            if(!n&&!m)
                break;
            for(i=1;i<=m;i++)
                for(j=1;j<=n;j++)
                    cin>>map[i][j];
            for(i=1;i<=m;i++)
                for(j=1;j<=n;j++)
                    if(map[i][j]=='@')
                    {
                        x=i;
                        y=j;
                        map[i][j]='.';
                    }
            cnt=0;
            memset(vis,0,sizeof(vis));
            dfs(x,y);
            printf("%d\n",cnt);
        }
        return 0;
    }