Scribd
Upload
18 views2 pages

第9题题解

The document contains C++ code that defines functions and variables to perform depth-first search (DFS) on a 2D vector map. It takes in the map dimensions m and n, populates the map with input values, and calls the dfs function starting from a given node (a-1, b-1). The dfs function recursively explores neighboring nodes, counting and marking visited nodes. It outputs the total number of visited nodes.

Uploaded by

1397710107
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
18 views2 pages

第9题题解

The document contains C++ code that defines functions and variables to perform depth-first search (DFS) on a 2D vector map. It takes in the map dimensions m and n, populates the map with input values, and calls the dfs function starting from a given node (a-1, b-1). The dfs function recursively explores neighboring nodes, counting and marking visited nodes. It outputs the total number of visited nodes.

Uploaded by

1397710107
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
You are on page 1/ 2

#include <bits/stdc++.

h>
using namespace std;
#define int long long
vector<vector<pair<int, int>>> MAP;
int m, n;
int num = 0;
int zzxc(int a, int b)
{
if (a < b)
{
int temp;
temp = a;
a = b;
b = temp;
}
int d = 1;
while (d)
{
d = a % b;
a = b;
b = d;
}
return a;
}
void dfs(int i, int j)
{
if (i < 0 || i >= m || j < 0 || j >= n)
return;
MAP[i][j].second = 1;
num++;
if (!(i + 1 < 0 || i + 1 >= m || j < 0 || j >= m) && MAP[i + 1][j].second != 1
&& zzxc(MAP[i][j].first, MAP[i + 1][j].first) > 1)
dfs(i + 1, j);
if (!(i - 1 < 0 || i - 1 >= m || j < 0 || j >= m) && MAP[i - 1][j].second != 1
&& zzxc(MAP[i][j].first, MAP[i - 1][j].first) > 1)
dfs(i - 1, j);
if (!(i < 0 || i >= m || j + 1 < 0 || j + 1 >= m) && MAP[i][j + 1].second != 1
&& zzxc(MAP[i][j].first, MAP[i][j + 1].first) > 1)
dfs(i, j + 1);
if (!(i < 0 || i >= m || j - 1 < 0 || j - 1 >= m) && MAP[i][j - 1].second != 1
&& zzxc(MAP[i][j].first, MAP[i][j - 1].first) > 1)
dfs(i, j - 1);
}
void solve()
{
cin >> m >> n;
MAP.resize(m);
for (vector<vector<pair<int, int>>>::iterator it = MAP.begin(); it !=
MAP.end(); it++)
{
vector<pair<int, int>> t(n);
for (vector<pair<int, int>>::iterator it2 = t.begin(); it2 != t.end(); it2+
+)
{
int temp;
cin >> temp;
*it2 = make_pair(temp, 0);
}
*it = t;
}
int a, b;
cin >> a >> b;
dfs(a - 1, b - 1);
cout << num;
}
signed main(void)
{
int _ = 1;
while (_--)
{
solve();
}
return 0;
}

You might also like