红与黑WrongAnswer 50

常规
1

1. 红与黑

XJOI - 题目ID：8120必做题100分

最新提交：

Wrong Answer

50 分

历史最高：

Wrong Answer

50 分

时间限制: 1000ms

空间限制: 524288kB

题目描述

这间长方形客房铺有方形瓷砖。每个瓷砖都是红色或黑色。一个男人站在黑色的瓷砖上。从瓷砖中，他可以移动到四个相邻瓷砖中的一个。但他不能在红瓦上移动，他只能在黑色瓷砖上移动。

输入格式

输入由多个数据集组成。数据集以包含两个正整数W和H的行开始; W和H分别是x和y方向上的瓦片数量。W和H不超过20.数据集中还有H行，每行包含W个字符。每个字符代表一个图块的颜色，如下所示。’ . ’ - 黑色瓷砖’＃’ - 红色瓷砖’@’ - 黑色瓷砖上的男人（在数据集中只显示一次）当遇到W和H为0的时候，代表输入数据结束。

输出格式

对于每个数据集，您的程序应输出一行，其中包含他可以从初始图块（包括其自身）到达的图块数量。

样例

Input 1

7 7
..#.#..
..#.#..
###.###
...@...
###.###
..#.#..
..#.#..
0 0

Output 1

13

Input 2

1 1
@
4 2
@###
...#
0 0

Output 2

1 
4

样例解释

他可以从初始图块（包括其自身）到达的图块数量为13。

数据范围

W和H分别是x和y方向上的瓦片数量。W和H不超过20.

#include<bits/stdc++.h>
using namespace std;
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
char mp[30][30];
int vis[30][30]={0},t=0;
int n,m,cnt,A,B,c=1;
void dfs(int x,int y);
int main()
{
	while(1)
	{
		c=1;A=0;B=0;cnt=0;n=0;m=0;t=0;
		cin>>m>>n;
		mp[30][30]={0};
		vis[30][30]={0}; 
		if(m==0 && n==0)return 0;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				cin>>mp[i][j];
				if(mp[i][j]=='@')
				{
					A=i;
					B=j;
				}
			}
		}
		vis[A][B]=1;
		dfs(A,B);
		cout<<c;
	}
	
}
void dfs(int x,int y)
{
	cnt++;
	for(int i=0;i<4;i++)
	{
		int nx=x+dx[i];
		int ny=y+dy[i];
		if(nx<1||nx>n||ny<1||ny>m||mp[nx][ny]=='#'||vis[nx][ny])
		{
			continue;
		}
		c++;
		vis[nx][ny]=1;
		dfs(nx,ny);
	}
}
2 个赞
2

你第16行的初始化不对：vis[i][j]={0};是这个值=0，而不是全初始化，介意改成：memset(vis,0,sizreof vis);

3 个赞
3

已经AC了，顺便说一句我错的原因是没加换行

3 个赞
4

6
不过memset(vis,0,sizreof vis);是有必要的

3 个赞
5

yes

3 个赞
6

顺便发一发题解:

#include<bits/stdc++.h>
using namespace std;
char maze[25][25];
int n,m,vis[25][25],s=99999999,sum,a,b;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
void dfs(int x,int y){
	sum++;
	vis[x][y]=1;		//避免回走，标记位置 
	for(int i=0;i<4;i++){	//四方枚举 
		int tx=x+dx[i];
		int ty=y+dy[i];
							//不越界。不撞墙。不回头 
		if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&maze[tx][ty]!='#'&&vis[tx][ty]==0){
			dfs(tx,ty);		//深搜前进 
		}
	}
	//vis[x][y]=0;			//该位置的枚举结束，撤销该位置的标记 
	}
int main(){
	while(cin>>m>>n){
		if(n==0&&m==0){
			break;
		}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>maze[i][j];
		}	
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(maze[i][j]=='@'){
				dfs(i,j);
				break;
			}		
		}	
	}
	cout<<sum<<endl;
	sum=0;
	memset(vis,0,sizeof(vis));
}
}
4 个赞
7

我能漂一个解决方案吗?

2 个赞