TopCoder SRM 637 Div2 GreaterGameDiv2

題目鏈接:https://www.topcoder.com/stat?c=problem_statement&pm=13507

題意

給一個n*m的矩陣,每個格子有一個元素,元素相同表示在同一個區域
開始所有格子都沒有顏色,Snuke選一些區域染成red,Sothe將剩下的區域染成blue
如果存在一條blue的路徑,從第一行到最後一行,那麼Sothe贏,否則Snuke贏
求使得Snuke贏將格子染成red的最小數量

解法

將一個區域看成一個點,每個店的權值為區域元素個數,
相鄰區域連一條邊,由於選定區域中的所有格子都要染色,
題目可以簡化成從第一列到最後一列的最短路徑,
起點和終點很多,所以重新添加新的起點和終點,
數據量不大,用floyd簡單點.

class ConnectingGameDiv2 {
  public:
    static const int N=300;
    int n,m;
    vector<string> board;
    int dis[N][N];
    int cost[N];
    void addedg(int i,int j,int x, int y)
    {
        if (x<0||y<0||x>=n||y>=m) return;
        int a=(int)board[i][j];
        int b=(int)board[x][y];
        dis[a][b]=min(dis[a][b],cost[a]); dis[b][a]=min(dis[b][a],cost[b]);
    }
    void init() {
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++) {
                dis[i][j]=10000;
            }
        }
    }
    int getmin(vector <string> board) {
        this->board=board;
        n=board.size();
        m=board[0].length();
        memset(cost,0,sizeof(cost));
        init();
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                int tmp=(int)board[i][j];
                cost[tmp]++;
            }
        }
        int st=0;
        int en=1;
        for(int i=0;i<N;i++) dis[i][i]=0;
        for(int i=0;i<n;i++) {
            int l=(int)board[i][0];
            int r=(int)board[i][m-1];
            dis[st][l]=0; dis[r][en]=cost[r];
        }
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                addedg(i,j,i+1,j); addedg(i,j,i-1,j); addedg(i,j,i,j+1); addedg(i,j,i,j-1);
                addedg(i,j,i+1,j+1); addedg(i,j,i-1,j-1); addedg(i,j,i+1,j-1); addedg(i,j,i-1,j+1);
            }
        }
        for(int k=0;k<N;k++) {
            for(int i=0;i<N;i++) {
                for(int j=0;j<N;j++) {
                    if(i==j||j==k||k==i) continue;
                    dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
                }
            }
        }
        return dis[st][en];
    }
};