一、红与黑

问题描述

有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向四周相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。

输入格式

第一行是两个整数 n 和 m，表示房间是 n 行 m 列大小(1<n,m<20)。在接下来的 n 行中，每行包括 m 个字符。每个字符表示一块瓷砖的颜色，规则如下: 1）‘.’：黑色的瓷砖； 2）‘#’：红色的瓷砖； 3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在数据中出现一次。

输出格式

一行，显示你从初始位置出发能到达的瓷砖数(注意：记数时包括初始位置的瓷砖)。

输入样例

5 6
....#.
.....#
......
#@...#
.#..#.

输出样例

21

#include<iostream>
using namespace std;
char mp[20][20];
int vis[20][20];//标记是否搜索，搜索过1 
int dx[4]={1,0,-1,0};//下右上左
int dy[4]={0,1,0,-1}; 
int n,m,ans=0;//连通块个数 
void dfs(int x,int y);
int main(){
	int sx,sy;//起点下标 
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>mp[i][j];
			if(mp[i][j]=='__(1)__'){
				sx=i;
				sy=j;
			}
		}
	}
	____(2)____;
	ans=1; 
	dfs(sx,sy);
	cout<<ans;
	return 0;
}
//深搜函数
void dfs(int x,int y){
	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&&____(3)____&&____(4)____){
			vis[nx][ny]=1;
			____(5)____;
			dfs(nx,ny);
		} 
	}
}

第 1 题

（1）处填写( ) {{ select(1) }}

• a
• @
• .
• d

---

第 2 题

（2）处填写( ) {{ select(2) }}

• vis[sx][sy]=1
• vis[sx][sy]=0
• ans=0
• int ans

---

第 3 题

（3）处填写( ) {{ select(3) }}

• vis[nx][ny]==1
• vis[nx][ny]==0
• mp[nx][ny]==0
• mp[nx][ny]==1

---

第 4 题

（4）处填写( ) {{ select(4) }}

• ny<=m
• mp[nx][ny]=='#'
• mp[nx][ny]!='#'
• ny>=1

---

第 5 题

（5）处填写( ) {{ select(5) }}

• ans++
• ans--
• sx++
• sy++

---

二、棋盘寻宝

问题描述

有一个n*m的棋盘（1 ≤ n,m ≤ 100），棋盘上有侍卫和宝藏，在棋盘的左上角（1,1）开始寻找宝藏，如果能避开侍卫找到宝藏输出YES，否则输出NO。 注意：左上角可能有侍卫，此题广度优先搜索解决。

输入格式

两个非零整数n和m，n表示迷阵行数，m表示迷阵列数。接下来有n行，每行包含m个符号，不同字符分别代表不同含义。 “.”：可以安全通行的方格，“#”：有守卫的方格，“*”：宝藏所在位置。

输出格式

找到宝藏输出YES，否则输出NO。

输入样例1

4 4
# . . .
. . . .
. . . *
. . . .

输出样例1

NO

输入样例2

4 4
. . . .
. # . #
. * . .
. . . .

输出样例2

YES

#include<bits/stdc++.h>
using namespace std;
struct node{
	int x,y;
};
char mp[101][101]; //地图 
int vis[101][101]={};//标记点是否被搜索过，搜过1 
queue<__(1)__> q;//队列 
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1}; 
int n,m;
//广搜函数
void bfs(){
	//1、起点入队
	node a={1,1};
	q.push(a); 
	vis[1][1]=1;//标记1，1点被搜索过
	while(___(3)____){//队列不为空 
		//2、获取队首元素，判断是否是宝藏 
		node f=q.front();
		if(mp[f.x][f.y]=='*'){
			cout<<"YES";
			return;//退出函数 
		} 
		//3、不是宝藏 ，相邻元素入队
		for(int i=0;i<4;i++){
			int nx=f.x+dx[i];
			int ny=f.y+dy[i];
			//如果没越界且不是障碍物且没被搜索过，可以入队
			if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&mp[nx][ny]!='#'&&vis[nx][ny]==0){
				vis[nx][ny]=1;//标记被搜索过
				___(4)____;
				q.push(r);//入队 
			} 
		} 
		//4、队首出队
		q.pop(); 
	} 
	___(5)___; 
} 
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>mp[i][j];
		}
	}
	//判断起点是否是守卫
	if(___(2)___){
		cout<<"NO";
		return 0;
	} 
	bfs();
	return 0;
}

第 6 题

（1）处填写( ) {{ select(6) }}

• int
• node
• char
• double

---

第 7 题

（2）处填写( ) {{ select(7) }}

• mp[1][1]=='.'
• mp[1][1]=='*'
• mp[1][1]=='#'
• mp[1][1]==0

---

第 8 题

（3）处填写( ) {{ select(8) }}

• q.empty()!=1
• a
• true
• false

---

第 9 题

（4）处填写( ) {{ select(9) }}

• node r=nx,ny
• node r=nx+1,ny+1
• node r={nx+1,ny+1}
• node r={nx,ny}

---

第 10 题

（5）处填写( ) {{ select(10) }}

• cout<<"YES"
• cout<<"NO"
• q.pop()
• q.empty()

---