[hihoCoder] 区域周长 解题报告 - Jonah的专栏 - 博客频道 - CSDN.NET
样例输入
给定一个包含 N × M 个单位正方形的矩阵,矩阵中每个正方形上都写有一个数字。
对于两个单位正方形 a 和 b ,如果 a 和 b 有一条共同的边,并且它们的数字相等,那么 a 和 b 是相连的。
相连还具有传递性,如果 a 和 b 相连,b 和 c 相连,那么 a 和 c 也相连。
给定一个单位正方形 s,s 和与 s 相连的所有单位正方形会组成一个区域 R 。小Hi想知道 R 的周长是多少?
输入
第一行包含4个整数 N , M ,x 和 y , N 和 M 是矩阵的大小, x 和 y 是给定的单位正方形 s 的坐标。(1 ≤ N , M ≤ 100, 0 ≤ x < N , 0 ≤ y < M )
以下是一个 N × M 的矩阵 A,Aij 表示相应的正方形上的数字。(0 ≤ Aij ≤ 100)
输出
输出一个整数表示 R 的周长。
6 5 2 1 0 0 1 2 2 3 1 1 3 7 4 3 1 3 7 4 3 0 3 2 4 3 3 0 1 4 5 5 5 5
- 样例输出
10
思路:求相邻正方形连成的周长,基本思路还是DFS.每找到一个未被访问过相邻的正方形周长+2,如果找到一个被访问过的正方形,周长-2.
在写代码的时候为了防止从A->B, 再从B->A, 我设置了一个数组来记录已经出现过的相邻的正方形.但其实没必要,只要在做DFS的时候判断一下不要回到上一个调用当前正方形的地方就行了.
int N, M, x, y,tem, ans=2; vector<vector<int> > map; vector<vector<set<int> > > neigh; void DFS(int x, int y,int preX, int preY, int val) { if(x<0 || x>=N || y<0 || y>=M ||map[x][y]!=val||neigh[x][y].count(preX*M+preY)) return; if(neigh[x][y].size() == 0) ans += 2; else ans -= 2; neigh[preX][preY].insert(x*M+y); neigh[x][y].insert(preX*M+preY); DFS( x+1, y, x, y, val); DFS( x-1, y, x, y, val); DFS( x, y+1, x, y, val); DFS( x, y-1, x, y, val); } int main() { cin >> N >> M >> x >> y; map.resize(N, vector<int>(M)); neigh.resize(N, vector<set<int> >(M)); for(int i = 0; i < N; i++) for(int j =0; j < M; j++) { cin >> tem; map[i][j] = tem; } DFS( x, y, x, y, map[x][y]); cout << ans << endl; return 0; }Read full article from [hihoCoder] 区域周长 解题报告 - Jonah的专栏 - 博客频道 - CSDN.NET