/* http://usaco.org/index.php?page=viewproblem2&cpid=596 (create a free account) USACO 2016 January Silver Ques. 3: Build Gates This code is not for Sololearn, I recommend onlinegdb.com or visual studio code Make a file named paint.in and put in: 14 NNNESWWWSSEEEE Output: 2 I recommend not copying this code into USACO though it works cause you need to do it yourself. */ #include #include #include #include #include #include #include using namespace std; int new_n; vector > farm; stack > st; vector > visited; void check(int new_r, int new_c){ if ((0 <= new_r && new_r < new_n) && \ (0 <= new_c && new_c < new_n) && \ !visited[new_r][new_c] && \ farm[new_r][new_c] == 0){ st.push(make_pair(new_r, new_c)); visited[new_r][new_c] = 1; } } int dfs(){ int result = 0; for(int rr = 0; rr < new_n; rr++){ for(int cc = 0; cc < new_n; cc++){ if(!visited[rr][cc] && farm[rr][cc] == 0){ cout << rr << " " << cc << endl; st.push(make_pair(rr, cc)); while(!st.empty()){ int r, c; r = st.top().first; c = st.top().second; st.pop(); visited[rr][cc] = 1; check(r - 1, c); check(r + 1, c); check(r, c - 1); check(r, c + 1); } result++; } } } return result - 1; } int main() { ifstream fin("gates.in"); ofstream fout("gates.out"); int n; fin >> n; new_n = n * 2 + 1; farm.resize(new_n, vector(new_n, 0)); visited.resize(new_n, vector(new_n, 0)); int row = new_n / 2, col = new_n / 2; string direct; fin >> direct; for(int i = 0; i < n; i++){ switch(direct[i]){ case 'N': row++; farm[row][col] = 1; row++; farm[row][col] = 1; break; case 'S': row--; farm[row][col] = 1; row--; farm[row][col] = 1; break; case 'W': col--; farm[row][col] = 1; col--; farm[row][col] = 1; break; case 'E': col++; farm[row][col] = 1; col++; farm[row][col] = 1; break; } } for (int i=0; i

USACO #23: Build Gates C++