[编程题]红与黑
- 热度指数：3204 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的（上下左右四个方向）黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。
输入描述:
输入包含多组数据。
每组数据第一行是两个整数 m 和 n（1≤m, n≤20）。紧接着 m 行，每行包括 n 个字符。每个字符表示一块瓷砖的颜色，规则如下：
1. “.”：黑色的瓷砖；
2. “#”：白色的瓷砖；
3. “@”：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。
输出描述:
对应每组数据，输出总共能够到达多少块黑色的瓷砖。
示例1
输入
9 6 ....#. .....# ...... ...... ...... ...... ...... #@...# .#..#.
输出
45
/*DFS 堆栈溢出
#include<iostream>
#include<vector> using namespace std;
char tile[20][20];
void DFS(int startx, int starty, int endx, int endy, int &curNum)
{
if (startx<0 || starty<0 || startx>endx || starty>endy || tile[startx][starty] == '#'){
// result = result<curNum ? curNum : result;
return;
}
if (tile[startx][starty] == '.')
curNum++;
tile[startx][starty] = '@';
int dx[4] = { 1, 0, 0, -1 };
int dy[4] = { 0, 1, -1, 0 };
for (int i = 0; i<4; i++)
DFS(startx + dx[i], starty + dy[i], endx, endy, curNum);
// curNum--;
// tile[startx][starty] = '.';
}
int main()
{
int m, n;
while (cin >> m >> n)
{
//vector<vector<char>> tile;
char t;
int startx = 0, starty = 0;
for (int i = 0; i<m; i++)
{
//vector<char> cur;
for (int j = 0; j<n; j++){
cin >> t;
tile[i][j]=t;
if (t == '@') { startx = i; starty = j; }
}
// tile.push_back(cur);
}
// int result = 0;
int curNum = 1;
DFS(startx, starty, m - 1, n - 1, curNum);
cout << curNum << endl;
} return 0;
}*/
//法二：BFS
#include<iostream>
#include<queue>
using namespace std;
char tile[20][20];
int dxy[4][2] = { 1, 0, 0, 1, 0, -1, -1, 0 };
struct node{
int x;
int y;
};
int main()
{
int rows, cols;
while (cin >> rows >> cols)
{
int startx = 0, starty = 0;
for (int i = 0; i<rows; i++)
{
for (int j = 0; j<cols; j++)
{
cin >> tile[i][j];
if (tile[i][j] == '@'){ startx = i; starty = j; }
}
}
queue<node> q;
int result = 1;
node cur;
cur.x = startx;
cur.y = starty;
q.push(cur);
while (!q.empty())
{
node temp = q.front();
q.pop();
for (int i = 0; i<4; i++)
{
node next;
next.x = temp.x + dxy[i][0];
next.y = temp.y + dxy[i][1];
if (next.x<rows&&next.x>=0&&next.y<cols&&next.y>=0&&tile[next.x][next.y] == '.')
{
result++;
q.push(next);
tile[next.x][next.y] = '@';
}
}
}
cout << result << endl; }
return 0;
}
发表于 2017-08-05 20:51:33
回复(2)
广度优先遍历
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<functional>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <exception>
#include <iomanip>
#include <memory>
#include <sstream>
using namespace std;
bool check(int x, int y, int m, int n, vector<vector<char>>& room)
{
return x >= 0 && x < m && y >= 0 && y < n && room[x][y] == '.';
}
int main(int argc, char** argv)
{
//freopen("in.txt", "r", stdin);
int m, n;
while (cin >> m >> n)
{
vector<vector<char>> room(m, vector<char>(n));
string row;
int sx, sy;
for (int i = 0; i < m; ++i)
{
cin >> row;
for (int j = 0; j < n; ++j)
{
room[i][j] = row[j];
if (room[i][j] == '@')
{
sx = i;
sy = j;
}
}
}
vector<pair<int, int>> cur;
cur.emplace_back(sx, sy);
int count = 1;
room[sx][sy] = ' ';
while (!cur.empty())
{
vector<pair<int, int>> next;
for (auto& pr : cur)
{
int x = pr.first, y = pr.second;
if (check(x - 1, y, m, n, room))
{
++count;
room[x - 1][y] = ' ';
next.emplace_back(x - 1, y);
}
if (check(x + 1, y, m, n, room))
{
++count;
room[x + 1][y] = ' ';
next.emplace_back(x + 1, y);
}
if (check(x, y - 1, m, n, room))
{
++count;
room[x][y - 1] = ' ';
next.emplace_back(x, y - 1);
}
if (check(x, y + 1, m, n, room))
{
++count;
room[x][y + 1] = ' ';
next.emplace_back(x, y + 1);
}
}
cur = next;
}
cout << count << endl;
}
return 0;
}
发表于 2017-07-10 22:00:08
回复(0)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int m = sc.nextInt();
int n = sc.nextInt();
sc.nextLine();
Character[][] map = new Character[m][n];
Node start = null;
for (int i = 0; i < m; i ++ ) {
String s = sc.nextLine();
for (int j = 0; j < n; j ++ ) {
map[i][j] = s.charAt(j);
if(s.charAt(j) == '@') start = new Node(i, j);
}
}
int[][] direction = {{0, 1}, {0, - 1}, {1, 0}, { - 1, 0}};
bfs(map, direction, start);
}
}
public static void bfs(Character[][] map, int[][] direction, Node start) {
Queue<Node> queue = new LinkedList<Node>();
boolean[][] visited = new boolean[map.length][map[0].length];
queue.add(start);
visited[start.x][start.y] = true;
int count = 1;
while ( ! queue.isEmpty()) {
Node cur = queue.poll();
for (int i = 0; i < 4; i ++ ) {
Node next = new Node(cur.x + direction[i][0], cur.y + direction[i][1]);
if(next.x >= 0 && next.x < map.length && next.y >= 0 && next.y < map[0].length && map[next.x][next.y] != '#' && ! visited[next.x][next.y]) {
count ++ ;
queue.add(next);
visited[next.x][next.y] = true;
}
}
}
System.out.println(count);
}
static class Node {
int x;
int y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
}
}
发表于 2016-10-08 18:03:44
回复(0)
//我用DFS爆栈了，下面是BFS
package test;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class BlackAndRed {
static boolean[][] visited;
static int count;
static int[][] direction = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int x = in.nextInt();
int y = in.nextInt();
int a = -1, b = -1;
char[][] ch = new char[x][y];
count=1;
visited = new boolean[x][y];
for (int i = 0; i < x; i++) {
String str = in.next();
for (int j = 0; j < y; j++) {
ch[i][j] = str.charAt(j);
if (ch[i][j] == '@') {
a = i;
b = j;
}
}
}
BFS(a, b, ch);
System.out.println(count);
}
}
public static void BFS(int x, int y, char[][] ch) {
Queue<Node> queue = new LinkedList<Node>();
queue.add(new Node(x, y));
visited[x][y] = true;
while (!queue.isEmpty()) {
Node cur = queue.poll();// 拿出队头
for (int i = 0; i < 4; i++) {
Node next = new Node(cur.x + direction[i][0], cur.y + direction[i][1]);
if (next.x >= 0 && next.x < ch.length && next.y >= 0 && next.y < ch[0].length
&& ch[next.x][next.y] != '#' && !visited[next.x][next.y]) {
count++;
queue.add(next);
visited[next.x][next.y] = true;
}
}
}
}
static class Node {
int x, y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
}
}
发表于 2016-10-26 12:53:31
回复(0)
#include<iostream>
#include<vector>
using namespace std;
int count=0;
void Result(vector<vector<char>>&arr,int x,int y)
{
if(x<0||x>=arr.size()||y<0||y>=arr[0].size()||arr[x][y]=='#')//走不通
return;
count++;
arr[x][y]='#';//走过之后也不能走了
Result(arr,x-1,y);//上下左右
Result(arr,x+1,y);
Result(arr,x,y-1);
Result(arr,x,y+1);
}
int main()
{
int m=0,n=0;
while(cin>>m>>n)
{
vector<vector<char>>v(m,vector<char>(n));
int x=0,y=0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
cin>>v[i][j];
if(v[i][j]=='@')
{
x=i;
y=j;
}
}
}
Result(v,x,y);
cout<<count<<endl;
count=0;
}
return 0;
}
编辑于 2020-03-10 13:39:40
回复(0)
//DFS算法
// 我是用一个二维int型数组a[20][20]来记录的（数组默认全为0）
//'.'记为0,'#'和'@'记为1（注意在输入的时候就可以判断）同时走过的格子也记为1
//那么对于一次DFS只要递归它的上、下、左、右4个相邻的格子就行
//由一个全局变量res记录结果
#include<iostream>
#include<string.h>
using namespace std;
int a[20][20] = {0},res = 0,m,n;//注意是全局变量，多组数据时要在最后初始化
void dfs(int x,int y)
{
if(a[x][y]==1||x<0||x>=m||y<0||y>=n)//递归的边界条件
return ;
res++; //结果增加1
a[x][y] = 1;//置1代表已经走过
dfs(x-1,y);//分别对应上
dfs(x+1,y);//下
dfs(x,y-1);//左
dfs(x,y+1);//右相邻格子
}
int main()
{
while(~scanf("%d %d",&m,&n))
{
getchar();//为什么要getchar()?因为第一行9 6后面还有一个换行符
int x,y;
char c;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
scanf("%c",&c);
if(c=='@')
{
x = i;
y = j;
}else{
if(c=='#')
a[i][j] = 1;
}
}
getchar();//同样的，吃掉每行最后一个换行符
}
dfs(x,y);
printf("%d\n",res);
res = 0;
memset(a,0,sizeof(a));//全局变量初始化
}
return 0;
}
编辑于 2018-04-02 21:29:44
回复(0)
// BFS广度优先搜索
import java.util.*;
public class Main{
static class Node{
int x, y;
public Node(int x, int y){
this.x = x;
this.y = y;
}
}
static int[][] direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
String[] str = sc.nextLine().split(" ");
int m = Integer.parseInt(str[0]);
int n = Integer.parseInt(str[1]);
char[][] tiles = new char[m][n];
// 利用boolean数组来记录走过的路以防重复
boolean[][] visited = new boolean[m][n];
// 开始的'@'就算做一个
int count = 1;
Node start = null;
for(int i = 0; i < m; i++){
String tmp = sc.nextLine();
for(int j = 0; j < n; j++){
tiles[i][j] = tmp.charAt(j);
if(tiles[i][j] == '@'){
start = new Node(i, j);
}
// 将'#'也视作走过了
if(tiles[i][j] == '#'){
visited[i][j] = true;
}
}
}
Queue<Node> queue = new LinkedList<>();
queue.offer(start);
visited[start.x][start.y] = true;
while(!queue.isEmpty()){
Node cur = queue.poll();
// 搜索节点cur的四个方向
for(int i = 0; i < 4; i++){
Node next = new Node(cur.x+direction[i][0], cur.y+direction[i][1]);
if(next.x >= 0 && next.x < m && next.y >= 0 && next.y < n
&& !visited[next.x][next.y]){
count++;
queue.offer(next);
visited[next.x][next.y] = true;
}
}
}
System.out.println(count);
}
}
}
// DFS深度优先搜索
import java.util.*;
public class Main{
static int count;
static int[][] direction = {{0,1}, {0,-1}, {1,0}, {-1,0}};
public static void dfs(int x, int y, char[][] tiles, int m, int n){
for(int i = 0; i < 4; i++){
int xx = x + direction[i][0];
int yy = y + direction[i][1];
if(xx >= 0 && xx < m && yy >= 0 && yy < n
&& tiles[xx][yy] == '.'){
count++;
tiles[xx][yy] = '#';
dfs(xx, yy, tiles, m, n);
}
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
String[] str = sc.nextLine().split(" ");
int m = Integer.parseInt(str[0]);
int n = Integer.parseInt(str[1]);
char[][] tiles = new char[m][n];
int startx = 0;
int starty = 0;
for(int i = 0; i < m; i++){
String tmp = sc.nextLine();
for(int j = 0; j < n; j++){
tiles[i][j] = tmp.charAt(j);
if(tiles[i][j] == '@'){
startx = i;
starty = j;
}
}
}
count = 1;
dfs(startx, starty, tiles, m, n);
System.out.println(count);
}
}
}
编辑于 2021-07-31 20:51:43
回复(0)
很模板的DFS
#include <iostream>
#include <vector>
using namespace std;
int maxBlack;
void DFS(int n, int m, vector<vector<char>>& map, vector<vector<int>>& route) {
if (map[n][m] == '#' || route[n][m] == 1)
return;
//n,m位置为黑方格且没走过
if (map[n][m] == '.' && route[n][m] == 0) {
maxBlack++;
route[n][m] = 1;
}
//右，上，左，下
if (m + 1 < map[0].size()) {
DFS(n, m + 1, map, route);
}
if (n - 1 >= 0) {
DFS(n - 1, m, map, route);
}
if (m - 1 >= 0) {
DFS(n, m - 1, map, route);
}
if (n + 1 < map.size()) {
DFS(n + 1, m, map, route);
}
}
int main() {
int n, m;
while (cin >> n >> m) {
//数组初始化
maxBlack = 1;
vector<vector<char>> map; //地图
vector<vector<int>> route; //走过的路线
map.resize(n, vector<char>(m));
route.resize(n, vector<int>(m, 0));
//起始位置
int on, om;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> map[i][j];
//确认初始位置
if (map[i][j] == '@') {
on = i;
om = j;
}
}
}
DFS(on, om, map, route);
cout << maxBlack << endl;
}
}
发表于 2024-06-16 15:59:34
回复(0)
#include<iostream>
#include<vector>
using namespace std;
int direct[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
void dfs(vector<vector<char>>& map,vector<vector<bool>>& flag,int row,int col,size_t& count)
{
//如果该位置已经遍历过了，则不用遍历
if(flag[row][col]){
return;
}
//遍历该位置
flag[row][col] = true;
//如果该位置是白色瓷砖，则停止搜索
if('#' == map[row][col]){
return;
}
//否则为黑色瓷砖
count++;
//然后继续向该位置的其他四个方向进行遍历
for(int i = 0; i < 4; i++){
int x = row + direct[i][0];
int y = col + direct[i][1];
if((x >=0 && x < map.size()) && (y >= 0 && y < map[0].size())){
dfs(map,flag,x,y,count);
}
}
}
int main()
{
int m,n;
while(cin >> m >> n)
{
//接收矩阵
vector<vector<char>> map(m,vector<char>(n));
//看该点如果是黑，且有没有被遍历过
vector<vector<bool>> flag(m,vector<bool>(n));
int row = 0,col = 0;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
cin >> map[i][j];
if(map[i][j] == '@'){
row = i;
col = j;
}
}
}
size_t count = 0;
dfs(map,flag,row,col,count);
cout << count << endl;
}
return 0;
}
发表于 2023-03-11 15:47:02
回复(0)
BFS
// write your code here cpp
#include<iostream>
#include<utility>
#include<vector>
#include<queue>
using namespace std;
int func(vector<vector<char>>& map)
{
int m=map.size();
int n=map[0].size();
int x;
int y;
int max=0;//记录最多黑砖
//找起点
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
if(map[i][j]=='@')
{
x=i;
y=j;
}
}
max++;
queue<pair<int,int>> vt;
vt.push(make_pair(x,y));
map[x][y]='*';//表示访问过，防止死循环
while(!vt.empty())
{
auto p = vt.front();
vt.pop();
x=p.first;
y=p.second;
const static int dx[]={1,-1,0,0};
const static int dy[]={0,0,1,-1};
for(int i=0;i<4;i++)
{
int newx=x+dx[i];
int newy=y+dy[i];
//坐标合法&&黑砖
if(newx>=0&&newx<m && newy>=0&&newy<n
&& map[newx][newy]=='.')
{
max++;
vt.push(make_pair(newx,newy));
map[newx][newy]='*';
}
}
}
return max;
}
int main()
{
int m;
int n;
while(cin>>m>>n)
{
vector<vector<char>> map(m,vector<char>(n));
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
cin>>map[i][j];
cout<<func(map)<<endl;
}
return 0;
}
发表于 2023-01-07 21:48:27
回复(0)
深度优先遍历
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNextInt()) {
int n = scanner.nextInt();
int m = scanner.nextInt();
String[] str = new String[n];
for (int i = 0; i < n; i++) {
str[i] = scanner.next();
}
int x=0;
boolean[][] flag = new boolean[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (str[i].charAt(j) == '@') {//起点位置
System.out.println(dfs(n, m, str, i, j, flag, 0));
x=1;
break;
}
}
if(x==1)
break;
}
}
}
private static int dfs ( int n, int m, String[] str,int i, int j, boolean[][] flag, int count){
if (i < 0 || i >= n || j < 0 || j >= m) {//越界
return 0;
}
if (str[i].charAt(j) == '#') {//如果是白色瓷砖 不可以走
return 0;
}
if (flag[i][j]) {//如果已经走过了
return 0;
}
if (str[i].charAt(j) == '.' || str[i].charAt(j) == '@') {//如果是黑色瓷砖
flag[i][j] = true;
//四个路径之和
count = count + 1 + dfs(n, m, str, i - 1, j, flag, count) + dfs(n, m, str, i + 1, j, flag, count) + dfs(n, m, str, i, j - 1, flag, count) + dfs(n, m, str, i, j + 1, flag, count);
}
return count;
}
}
发表于 2022-09-21 15:09:37
回复(0)
广度优先遍历
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
Deque<Cool> que = new LinkedList<>();
int max = 0;
int row = sc.nextInt();
int col = sc.nextInt();
int x = 0 , y = 0;
String[][] map = new String[row][col];
for(int i = 0;i < row;i++){
char[] chArr = sc.next().toCharArray();
for(int j = 0;j < col; j++){
map[i][j] = chArr[j]+"";
if(chArr[j] == '@'){
x = i;
y = j;
}
}
}
que.add(new Cool(x,y));
while(!que.isEmpty()){
Cool co = que.poll();
x = co.x;
y = co.y;
if("#".equals(map[x][y])){
continue;
}
map[x][y] = "#";
max++;
if(x+1 < row && ".".equals(map[x+1][y])){
que.add(new Cool(x+1,y));
}
if(x-1 >= 0 && ".".equals(map[x-1][y])){
que.add(new Cool(x-1,y));
}
if(y+1 < col && ".".equals(map[x][y+1])){
que.add(new Cool(x,y+1));
}
if(y-1 >= 0 && ".".equals(map[x][y-1])){
que.add(new Cool(x,y-1));
}
}
System.out.println(max);
}
}
private static class Cool{
private final int x;
private final int y;
public Cool(int x,int y){
this.x = x;
this.y = y;
}
}
}
发表于 2022-05-17 16:01:29
回复(0)
import java.util.*;
public class Main{
public static int count = 0;
public static int[][] dir = {{-1,0},{1,0},{0,1},{0,-1}};
public static void dfs(char[][] map,int m,int n,int x,int y){
if(map[x][y] == '#'){
return;
}
count++;
map[x][y] = '#';
for(int i = 0;i < 4;i++){
int xx = x + dir[i][0];
int yy = y + dir[i][1];
if(xx >= 0 && xx < m && yy >= 0 && yy < n
){
dfs(map,m,n,xx,yy);
}
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int m = sc.nextInt();
int n = sc.nextInt();
char[][] map = new char[m][n];
int x = 0;
int y = 0;
for(int i = 0;i < m;i++){
String s = sc.next();
for(int j = 0;j < n;j++){
map[i][j] = s.charAt(j);
//找到刚开始所站的位置
if(map[i][j] == '@'){
x = i;
y = j;
}
}
}
count = 0;
dfs(map,m,n,x,y);
System.out.println(count);
}
}
} import java.util.*;
public class Main{
public static int count = 0;
public static int[][] dir = {{-1,0},{1,0},{0,1},{0,-1}};
public static void dfs(char[][] map,int m,int n,int x,int y){
for(int i = 0;i < 4;i++){
int xx = x + dir[i][0];
int yy = y + dir[i][1];
if(xx >= 0 && xx < m && yy >= 0 && yy < n
&& map[xx][yy] == '.'){
count++;
map[xx][yy] = '#';
dfs(map,m,n,xx,yy);
}
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int m = sc.nextInt();
int n = sc.nextInt();
char[][] map = new char[m][n];
int x = 0;
int y = 0;
for(int i = 0;i < m;i++){
String s = sc.next();
for(int j = 0;j < n;j++){
map[i][j] = s.charAt(j);
//找到刚开始所站的位置
if(map[i][j] == '@'){
x = i;
y = j;
}
}
}
count = 1;
dfs(map,m,n,x,y);
System.out.println(count);
}
}
}
编辑于 2022-06-01 10:35:31
回复(0)
import java.util.Scanner;
public class Main {
static boolean[][] flag;
static int ans = 0;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int row = scanner.nextInt();
int col = scanner.nextInt();
int m = 0, n = 0;
ans = 0;
flag = new boolean[row][col];
char[][] map = new char[row][col];
for (int i = 0; i < row; i++) {
String tmp = scanner.next();
for (int j = 0; j < col; j++) {
map[i][j] = tmp.charAt(j);
flag[i][j] = false;
if (map[i][j] == '@') {
m = i;
n = j;
}
}
}
findBlack(map, m, n);
System.out.println(ans);
}
}
public static void findBlack(char[][] map, int m, int n) {
if (m >= map.length || n >= map[0].length || m < 0 || n < 0 || map[m][n] == '#') {
return;
}
if (flag[m][n]) {
return;
}
ans++;
flag[m][n] = true;
findBlack(map, m + 1, n);
findBlack(map, m, n + 1);
findBlack(map, m, n - 1);
findBlack(map, m - 1, n);
}
}
发表于 2022-04-12 22:37:14
回复(0)
dfs 与bfs
// write your code here cpp
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int dx[]={0,1,0,-1}, dy[]={1,0,-1,0};
int ret=0;
typedef pair<int,int> PII;
queue<PII> q;
void dfs(vector<vector<char>>& board,int x,int y,int m,int n)
{
ret++;
board[x][y]='#';
for(int i=0;i<4;i++)
{
int new_x=x+dx[i],new_y=y+dy[i];
if(new_x>=0 && new_x<m && new_y>=0 && new_y<n && board[new_x][new_y]=='.')
{
dfs(board,new_x,new_y,m,n);
}
}
}
void bfs(vector<vector<char>>& board,int m,int n)
{
while(!q.empty())
{
PII cur=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int new_x=cur.first+dx[i],new_y=cur.second+dy[i];
if(new_x>=0 && new_x<m && new_y>=0 && new_y<n && board[new_x][new_y]=='.')
{
ret++;
q.push({new_x,new_y});
board[new_x][new_y]='#';
}
}
}
}
int main()
{
int m,n;
while(cin>>m>>n)
{
vector<vector<char>> board(m,vector<char>(n));
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
cin>>board[i][j];
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
{
if(board[i][j]=='@')
{
//dfs(board,i,j,m,n);
q.push({i,j});
ret++;
bfs(board,m,n);
cout<<ret<<endl;
}
}
ret=0;
}
return 0;
}
发表于 2020-07-16 12:27:10
回复(0)
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int arr[] = { -1,0,1 };
int getnum(vector<vector<int>>& ret, int i, int j)
{
ret[i][j] = 0;
int sum = 1;
for (int a = 0; a < 3; ++a)
{
for (int b = 0; b < 3; ++b)
{
if (i + arr[a] < ret.size() && i + arr[a] >= 0 && j + arr[b] < ret[0].size() && j + arr[b] >= 0 && ret[i + arr[a]][j + arr[b]]&&abs(arr[a])!=abs(arr[b]))
sum+=getnum(ret, i + arr[a], j + arr[b]);
}
}
return sum;
}
int main()
{
int m, n;
while (cin >> m >> n)
{
vector<string> str;
int num = 0;
string temp;
vector<vector<int>> ret(m, vector<int>(n, 1));
cin.get();
for (int i = 0; i<m; ++i)
{
getline(cin, temp);
str.push_back(temp);
}
int n1=0, n2=0;
for (int i = 0; i<m; ++i)
{
for (int j = 0; j<n; ++j)
{
if (str[i][j] == '#')
ret[i][j] = 0;
if (str[i][j] == '@')
{
n1 = i;
n2 = j;
}
}
}
cout << getnum(ret, n1, n2) << endl;
}
return 0;
} 利用{-1，0，1}数组完成对四个格子的遍历
发表于 2020-06-08 20:26:37
回复(0)
#include<vector>
#include<iostream>
#include<string>
using namespace std;
int index[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
int cnt;
void DFS(vector<vector<int>>& book,vector<string>& board,int start_row,int start_col,int row,int col){
if((board[start_row][start_col]=='.'&& book[start_row][start_col] == 0) || board[start_row][start_col] == '@')
cnt++;
if(board[start_row][start_col]=='#')
return;
//将当前的坐标先进行标记
book[start_row][start_col] = 1;
//进行深度优先遍历
for(int k = 0; k < 4; ++k){
int new_row = start_row + index[k][0];
int new_col = start_col + index[k][1];
if(new_row < 0 || new_row >= row || new_col < 0 || new_col >= col){
continue;
}
if(board[new_row][new_col] == '.' && book[new_row][new_col] == 0){
DFS(book,board,new_row,new_col,row,col);
}
}
}
int main(){
int N,M;
while(cin >> N >> M){
//构建二维矩阵
vector<string> path(N);
vector<vector<int>> book(N,vector<int>(M,0));
for(auto& e : path){
cin >> e;
}
//找到‘@’起始位置
for(int i = 0; i < N; ++i){
for(int j = 0; j < path[0].size(); ++j){
if(path[i][j]=='@'){
//进行深度优先遍历
DFS(book,path,i,j,N,M);
}
}
}
cout << cnt << endl;
cnt=0;
}
return 0;
}
#include<iostream>
#include<string>
using namespace std;
int index[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
int cnt;
void DFS(vector<vector<int>>& book,vector<string>& board,int start_row,int start_col,int row,int col){
if((board[start_row][start_col]=='.'&& book[start_row][start_col] == 0) || board[start_row][start_col] == '@')
cnt++;
if(board[start_row][start_col]=='#')
return;
//将当前的坐标先进行标记
book[start_row][start_col] = 1;
//进行深度优先遍历
for(int k = 0; k < 4; ++k){
int new_row = start_row + index[k][0];
int new_col = start_col + index[k][1];
if(new_row < 0 || new_row >= row || new_col < 0 || new_col >= col){
continue;
}
if(board[new_row][new_col] == '.' && book[new_row][new_col] == 0){
DFS(book,board,new_row,new_col,row,col);
}
}
}
int main(){
int N,M;
while(cin >> N >> M){
//构建二维矩阵
vector<string> path(N);
vector<vector<int>> book(N,vector<int>(M,0));
for(auto& e : path){
cin >> e;
}
//找到‘@’起始位置
for(int i = 0; i < N; ++i){
for(int j = 0; j < path[0].size(); ++j){
if(path[i][j]=='@'){
//进行深度优先遍历
DFS(book,path,i,j,N,M);
}
}
}
cout << cnt << endl;
cnt=0;
}
return 0;
}
#include<vector>
#include<iostream>
#include<string>
using namespace std;
int index[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
int cnt;
void DFS(vector<vector<int>>& book,vector<string>& board,int start_row,int start_col,int row,int col){
if((board[start_row][start_col]=='.'&& book[start_row][start_col] == 0) || board[start_row][start_col] == '@')
cnt++;
if(board[start_row][start_col]=='#')
return;
//将当前的坐标先进行标记
book[start_row][start_col] = 1;
//进行深度优先遍历
for(int k = 0; k < 4; ++k){
int new_row = start_row + index[k][0];
int new_col = start_col + index[k][1];
if(new_row < 0 || new_row >= row || new_col < 0 || new_col >= col){
continue;
}
if(board[new_row][new_col] == '.' && book[new_row][new_col] == 0){
DFS(book,board,new_row,new_col,row,col);
}
}
}
int main(){
int N,M;
while(cin >> N >> M){
//构建二维矩阵
vector<string> path(N);
vector<vector<int>> book(N,vector<int>(M,0));
for(auto& e : path){
cin >> e;
}
//找到‘@’起始位置
for(int i = 0; i < N; ++i){
for(int j = 0; j < path[0].size(); ++j){
if(path[i][j]=='@'){
//进行深度优先遍历
DFS(book,path,i,j,N,M);
}
}
}
cout << cnt << endl;
cnt=0;
}
return 0;
}
发表于 2019-08-04 21:06:48
回复(0)
// write your code here cpp
#include<iostream>
#include<vector>
using namespace std;
//通过vector创建的二维数组进行递归调用，把已经走过的结点标记成'1',避免访问过的
//结点重复计数
void BlackCount(vector<vector<char>>& v,int x,int y,int m,int n,int& count)
{
//count通过引用的方式，正好递归调用进行计数
if(x<0||y<0||x>=m||y>=n||v[x][y]=='1'||v[x][y]=='#')
return;
count++;
v[x][y]='1';
BlackCount(v,x-1,y,m,n,count);
BlackCount(v,x,y-1,m,n,count);
BlackCount(v,x+1,y,m,n,count);
BlackCount(v,x,y+1,m,n,count);
}
int main()
{
int m,n;
while(cin>>m>>n)
{
int x,y;
int count=0;
vector<vector<char>> v(m,vector<char>(n,0));
for(size_t i=0;i<m;i++)
{
for(size_t j=0;j<n;j++)
{
cin>>v[i][j];
if(v[i][j]=='@')
{
x=i;//x标记起始i结点
y=j;//y表示起始j结点
}
}
}
BlackCount(v,x,y,m,n,count);
cout<<count<<endl;
}
return 0;
}
发表于 2019-07-23 15:40:24
回复(0)
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
while(scan.hasNext()){
int m=scan.nextInt();
int n=scan.nextInt();
scan.nextLine();
boolean map[][]=new boolean [m][n];
int si=-1;
int sj=-1;
for(int i=0;i<m;i++){
char[] temp=scan.nextLine().toCharArray();
for(int j=0;j<n;j++){
if(temp[j]=='@'){
map[i][j]=true;
si=i;
sj=j;
}else if(temp[j]=='#'){
map[i][j]=false;
}else{
map[i][j]=true;
}
}
}
System.out.println(helper(map,si,sj));
}
}
public static int helper(boolean map[][],int si,int sj){
boolean c[][]=new boolean [map.length][map[0].length];
Queue<Integer> qi=new LinkedList<Integer>();
Queue<Integer> qj=new LinkedList<Integer>();
qi.add(si);
qj.add(sj);
c[si][sj]=true;
while(!qi.isEmpty()){
int i=qi.poll();
int j=qj.poll();
if(i-1>=0&&map[i-1][j]==true&&c[i-1][j]==false){
qi.add(i-1);
qj.add(j);
c[i-1][j]=true;
}
if(i+1<map.length&&map[i+1][j]==true&&c[i+1][j]==false){
qi.add(i+1);
qj.add(j);
c[i+1][j]=true;
}
if(j-1>=0&&map[i][j-1]==true&&c[i][j-1]==false){
qi.add(i);
qj.add(j-1);
c[i][j-1]=true;
}
if(j+1<map[0].length&&map[i][j+1]==true&&c[i][j+1]==false){
qi.add(i);
qj.add(j+1);
c[i][j+1]=true;
}
}
int count=0;
for(int i=0;i<map.length;i++){
for(int j=0;j<map[0].length;j++){
if(c[i][j]==true){
count++;
}
}
}
return count;
}
}
发表于 2017-04-06 15:01:23
回复(0)
没别的 DFS
#include<iostream>
using namespace std;
char map[21][21];
int dir[4][2]={-1,0,1,0,0,-1,0,1};
bool visited[21][21];
void game(int x,int y,int m,int n,int &step)
{
for(int i=0;i<4;i++)
{
int nx=x+dir[i][0];
int ny=y+dir[i][1];
if(nx>=1&&nx<=m&&ny>=1&&ny<=n&&visited[nx][ny]==false&&map[nx][ny]=='.')
{
visited[nx][ny]=true;
game(nx,ny,m,n,step=step+1);
}
}
}
int main()
{
int m,n;
while(cin>>m>>n)
{
int cx,cy,step=1;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
visited[i][j]=false;
cin>>map[i][j];
if(map[i][j]=='@')
{
cx=i;cy=j;
}
}
visited[cx][cy]=true;
game(cx,cy,m,n,step);
cout<<step<<endl;
}
return 0;
}
发表于 2017-03-30 17:58:30
回复(0)
问题信息
难度：
23条回答
29收藏
13124浏览
通过挑战的用户
查看代码-
2023-03-11 16:07:49 -
2023-03-05 11:54:15
-
2023-02-07 21:06:08 -
2023-02-04 21:25:46
-
2023-01-07 21:44:20
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
