jeudi 21 février 2019

How could I optimize this Multiplayer Moo (USACO US Open Silver Prob. 3) code?

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