Saturday, June 4, 2016
C++ Solution to UVA 352 - The Seasonal War using 2D Array Depth First Search
June 04, 2016
2d array traversal
,
352
,
array bound checking with direction arrays
,
beginner
,
connected components count
,
cpp
,
depth first search maze
,
dfs
,
easy
,
explanation
,
graph algorithm
,
solution
,
The Seasonal War
,
uva
Problem Link:
https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=288Problem Explanation & Visalization:
TODOInput & Output Explanation:
TODOInput & Output:
Input:6 100100 001010 000000 110000 111000 010100 8 01100101 01000001 00011000 00000010 11000011 10100010 10000001 01100000
Output:Image number 1 contains 3 war eagles. Image number 2 contains 6 war eagles.
More input and output in udebug:
https://www.udebug.com/UVa/352Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Author: Asif Ahmed | |
| * Site: http://quickgrid.blogspot.com | |
| * Description: Find out number of connected components. | |
| */ | |
| #include<bits/stdc++.h> | |
| using namespace std; | |
| #define M 26 | |
| static int picture[M][M]; | |
| static bool visited[M][M]; | |
| static char temp[M]; | |
| int n; | |
| // Check all 8 direction co-ordinates. | |
| // N, NE, E, SE, S, SW, W, NW | |
| static int dr[] = {-1, -1, 0, 1, 1, 1, 0, -1}; | |
| static int dc[] = {0, 1, 1, 1, 0, -1, -1, -1}; | |
| // DFS visit. Call on each node that has node been visited. | |
| // This code below traverses all the nodes connected with given node. | |
| void visit(int i, int j){ | |
| visited[i][j] = true; | |
| for( int k = 0; k < 8; ++k ){ | |
| if( i + dr[k] >= 0 && i + dr[k] < n && j + dc[k] >= 0 && j + dc[k] < n ){ | |
| int ti = i + dr[k]; | |
| int tj = j + dc[k]; | |
| if( !visited[ti][tj] && picture[ti][tj] ){ | |
| visit(ti, tj); | |
| } | |
| } | |
| } | |
| } | |
| int main(){ | |
| // | |
| //freopen("input.txt", "r", stdin); | |
| //freopen("output.txt", "w", stdout); | |
| // | |
| int c = 0; | |
| while(scanf("%d", &n) == 1){ | |
| getchar(); | |
| for(int i = 0; i < n; ++i){ | |
| scanf("%s", temp); | |
| for(int j = 0; j < n; ++j){ | |
| picture[i][j] = temp[j] - '0'; | |
| visited[i][j] = false; | |
| } | |
| } | |
| // DFS | |
| // Call for each of the nodes in 2D graph that has not been visited by DFS visit. | |
| // The number of unvisited nodes here is the connected component count. | |
| int connectedComponents = 0; | |
| for( int i = 0; i < n; ++i ){ | |
| for( int j = 0; j < n; ++j ){ | |
| if( !visited[i][j] && picture[i][j] ){ | |
| ++connectedComponents; | |
| visit(i,j); | |
| } | |
| } | |
| } | |
| printf("Image number %d contains %d war eagles.\n", ++c, connectedComponents); | |
| } | |
| return 0; | |
| } |
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment