I wrote this code for USACO 2018 US Open problem. I got 9/10 cases correct, except for the the 9th one, which couldn't run in time.
I have attached my code below. Could you please help me find a way to optimize my code?
#include <map>
#include <vector>
#include <fstream>
#include <iostream>
using namespace std;
#define MAX_COWS 255
typedef pair <int,int> pii;
int grid [MAX_COWS][MAX_COWS],regions[MAX_COWS][MAX_COWS],n,regionID = 1,tempArea,combinedArea;
map <int,vector <pii>> neighbors;
map <int,int> sizeOfRegion,IDofRegion;
map <int,int> visited;
int changeX [] = {-1,1,0,0}; //Used for my Floodfill DFS (Up,Down,Left,Right coordinate changes)
int changeY [] = {0,0,-1,1};
void flood(int r, int c, int id)
{
if(r < 1 || r > n || c < 1 || c > n || regions[r][c] == regionID) //Boundary Condition or Visited Condition
return;
if(grid[r][c] != id) //If we have arrived at a neighboring cell, note it as a neighbor and return
{
neighbors[regionID].push_back(make_pair(r,c));
return;
}
regions[r][c] = regionID; //Creating our lookup table
tempArea++;
for(int i = 0; i < 4; i++) //DFS Floodfill
{
int n_x = r + changeX[i],n_y = c + changeY[i];
flood(n_x,n_y,id);
}
}
void dfs(int region,int key1,int key2,int visitedNumber)
{
if(visited[region] == visitedNumber) //If we have already traversed this region
return;
tempArea += sizeOfRegion[region]; //Incrementing by region
visited[region] = visitedNumber;
for(auto it : neighbors[region]) //Testing all neighbors of this node
{
int neighboringRegionReference = regions[it.first][it.second];
if(IDofRegion[neighboringRegionReference] == key1 || IDofRegion[neighboringRegionReference] == key2)
dfs(neighboringRegionReference,key1,key2,visitedNumber);
}
}
int main()
{
ifstream fin ("multimoo.in");
fin >> n;
for(int i = 1;i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
fin >> grid[i][j];
}
}
int maxRegion = 0;
for(int i = 1;i <= n; i++) //Identifying each region through a floodfill
{
for(int j = 1; j <= n; j++)
{
if(!regions[i][j])
{
tempArea = 0; //I am not proficient with writing a floodfill that can return values, so I used a temporary variable to retrieve info
flood(i,j,grid[i][j]); //Floodfill
//printNeighbors(regionID);
sizeOfRegion[regionID] = tempArea; //Map that stores size of reach region
maxRegion = max(maxRegion,sizeOfRegion[regionID]); // Answer 1 (First Number)
IDofRegion[regionID] = grid[i][j]; //Creating a lookup table for second problem
regionID++; //Incrementing index
}
}
}
for(int i = 1; i < regionID; i++)
{
visited[i] = i; //We have already 'visited' this node
for(auto it : neighbors[i])
{
tempArea = sizeOfRegion[i]; //Again, a temp variable to retrieve information from future DFS
int neighboringRegionReference = regions[it.first][it.second]; //Taking the information and retrieving region from lookup grid
dfs(neighboringRegionReference,IDofRegion[neighboringRegionReference],IDofRegion[i],i);
combinedArea = max(combinedArea,tempArea);
}
}
ofstream fout ("multimoo.out");
fout << maxRegion << "\n" << combinedArea << endl;
}
I was thinking of switching my 'visited' map to an array and manually initializing it. Would this help? Is there anything else I could do?
Aucun commentaire:
Enregistrer un commentaire