Codeforces Round #108(Div.2)-상태 압축 DP+spfa+dfs-Garden

6168 단어 codeforces
Vasya has a very beautiful country garden that can be represented as an n × m rectangular field divided into n·m squares. One beautiful day Vasya remembered that he needs to pave roads between k important squares that contain buildings. To pave a road, he can cover some squares of his garden with concrete.
For each garden square we know number aij that represents the number of flowers that grow in the square with coordinates (i, j). When a square is covered with concrete, all flowers that grow in the square die.
Vasya wants to cover some squares with concrete so that the following conditions were fulfilled:
  • all k important squares should necessarily be covered with concrete
  • from each important square there should be a way to any other important square. The way should go be paved with concrete-covered squares considering that neighboring squares are squares that have a common side
  • the total number of dead plants should be minimum

  • As Vasya has a rather large garden, he asks you to help him.
    Input
    The first input line contains three integers n, m and k (1 ≤ n, m ≤ 100, n·m ≤ 200, 1 ≤ k ≤ min(n·m, 7)) — the garden's sizes and the number of the important squares. Each of the next n lines contains m numbers aij (1 ≤ aij ≤ 1000) — the numbers of flowers in the squares. Next k lines contain coordinates of important squares written as "x y"(without quotes) (1 ≤ x ≤ n, 1 ≤ y ≤ m). The numbers written on one line are separated by spaces. It is guaranteed that all k important squares have different coordinates.
    Output
    In the first line print the single integer — the minimum number of plants that die during the road construction. Then print n lines each containing m characters — the garden's plan. In this plan use character "X"(uppercase Latin letter X) to represent a concrete-covered square and use character "."(dot) for a square that isn't covered with concrete. If there are multiple solutions, print any of them.
    Sample test(s)
    input
    3 3 2
    1 2 3
    1 2 3
    1 2 3
    1 2
    3 3

    output
    9
    .X.
    .X.
    .XX

    input
    4 5 4
    1 4 5 1 2
    2 2 2 2 7
    2 4 1 4 5
    3 2 1 7 1
    1 1
    1 5
    4 1
    4 4

    output
    26
    X..XX
    XXXX.
    X.X..
    X.XX.
    http://blog.csdn.net/gzh1992n/article/details/9119543
    /*
    
      : k         ,     
    
     dp[i][j]      i  ,    j               
    
                
    
    1:     dp[i][j] = min(dp[k][j] + maze[k][i])       ,     
    
    2:     dp[i][j] = min(dp[i][j1] + dp[i][j2] - maze[i/m][i%m]) j1,j2 j   
    
    dfs   
    
    */
    
    #include <iostream>
    
    #include <cstdio>
    
    #include <cstring>
    
    #include <algorithm>
    
    #include <vector>
    
    #include <queue>
    
    #include <cmath>
    
    #include <string>
    
    #include <map>
    
    using namespace std;
    
    const int inf = 1 << 29;
    
    const int MAX = 200 + 10;
    
    int dp[MAX][1<<7], pre[MAX][1<<7];
    
    int n, m, k, nn, mm;
    
    int hash1[MAX];
    
    int maz[MAX][MAX];
    
    char g[MAX][MAX];
    
    bool visit[MAX][1<<7];
    
    int dx[] = {0, 0, -1, 1};
    
    int dy[] = {-1, 1, 0, 0};
    
    
    
    struct Node {
    
        int u, st;
    
        Node(int _u, int _st){
    
                u = _u, st = _st;//      
    
        }
    
    };
    
    queue<Node> que;
    
    
    
    bool check(int x, int y) {
    
        if(x >= 0 && x < n && y >= 0 && y < m) return true;
    
        return false;
    
    }
    
    
    
    //update(u, hash[u], maz[a][b], -1);
    
    void update(int u, int st, int w, int fa) {
    
        if(dp[u][st] > w) {
    
            dp[u][st] = w;
    
            pre[u][st] = fa;//    
    
            if(!visit[u][st]) {
    
                que.push(Node(u, st));
    
                visit[u][st] = true;
    
            }
    
        } 
    
    } 
    
    
    
    void dfs(int u, int st) {
    
        int x = u / m, y = u % m;
    
        g[x][y] = 'X';
    
        if(pre[u][st] == -1) return;//           
    
        else {
    
            int v = pre[u][st] / 1000, stt = pre[u][st] % 1000;
    
            dfs(v, stt);
    
            if(stt - st) dfs(v, st - stt);//      
    
        }
    
    }
    
    
    
    void solve() {//spfa
    
        while(!que.empty()) {
    
            Node now = que.front();
    
            que.pop();
    
            int u = now.u, x = now.u / m, y = now.u % m, st = now.st;
    
            visit[u][st] = false;//     
    
            for(int i = 0; i < 4; i++) {
    
                int xx = x + dx[i], yy = y + dy[i];
    
                if(!check(xx, yy)) continue;
    
                int v = xx * m + yy;
    
                update(v, st, dp[u][st] + maz[xx][yy], u * 1000 + st);//      
    
            }
    
            int t = mm - 1 - st;
    
            for(int i = t; i; i = (i-1) & t) {
    
                update(u, i | st, dp[u][i] + dp[u][st] - maz[x][y], u * 1000 + st);//       ,             
    
            }
    
        }
    
        int ans = inf, u;
    
        for(int i = 0; i < nn; i++) {
    
            if(ans > dp[i][mm-1]) {
    
                ans = dp[i][mm-1];
    
                u = i;
    
            }
    
        }//      
    
        dfs(u, mm - 1);//DFS   
    
        cout << ans << endl;
    
        for(int i = 0; i < n; i++) {
    
            for(int j = 0; j < m; j++)
    
                cout << g[i][j];
    
            cout << endl;
    
        }
    
    }
    
    
    
    int main() {
    
        while(cin >> n >> m >> k) {
    
            while(!que.empty()) que.pop();
    
            for(int i = 0; i < n; i++) {
    
                for(int j = 0; j < m; j++) {
    
                    cin >> maz[i][j];
    
                    g[i][j] = '.';//    
    
                }
    
            }
    
            nn = n * m, mm = 1 << k;//    
    
            memset(hash1, 0, sizeof(hash1));
    
            memset(visit, false, sizeof(visit));
    
            for(int i = 0; i < nn; i++) 
    
                for(int j = 0; j < mm; j++)
    
                    dp[i][j] = inf;//     ,        
    
            for(int i = 0, a, b; i < k; i++) {
    
                cin >> a >> b;
    
                a--, b--;
    
                int u = a * m + b;
    
                hash1[u] = 1 << i;//    
    
                update(u, hash1[u], maz[a][b], -1);
    
            }
    
            solve();
    
        }
    
        return 0;
    
    }
    
    

      

    좋은 웹페이지 즐겨찾기