• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            Tim's Programming Space  
            Tim's Programming Space
            日歷
            <2010年7月>
            27282930123
            45678910
            11121314151617
            18192021222324
            25262728293031
            1234567
            統(tǒng)計(jì)
            • 隨筆 - 20
            • 文章 - 1
            • 評(píng)論 - 40
            • 引用 - 0

            導(dǎo)航

            常用鏈接

            留言簿(3)

            隨筆檔案

            文章檔案

            搜索

            •  

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

             

            The Alliances

            In a fantasy world, there is a large island of a rectangular shape. The sides of the island happen to be exactly R miles and C miles long, and the whole island is divided into a grid of R\times C areas. Some of the areas are uninhabited, and the rest are occupied by villages of fantasy beings: elves, humans, dwarves, and hobbits. Each area contains at most one village. Two villages are considered neighbours if their areas share a side.

            Recently, the villages became terrified of the Great Evil. In order to feel safer, each village has decided to form military alliances with some of its neighbours. An alliance always involves two neighbouring villages, and it is a mutual and symmetric agreement.

            Depending on the species living in the village, the inhabitants will not feel safe unless a specific configuration of alliances is formed:

            • The elves feel confident, and therefore need exactly one alliance.
            • Human villages require alliances with exactly two neighbours.
              Moreover, leaving two opposite sides of the village exposed is bad for tactical reasons. Therefore the two allied neighbours cannot be located on opposite sides of the village.
            • Dwarves require alliances with exactly three neighbours.
            • Hobbits are extremely scared, and therefore need to have alliances with all four of their neighbours.

            In other words, except for humans each village requires a particular number of alliances, but does not care which neighbours will be its allies. For humans there is an additional restriction: the allied neighbours must not be on opposite sides of the village.

            The conditions must be fulfilled irrespective of the position of the village on the map. For example, a dwarf village desires three alliances. If it is located on the coast, this means that it must have alliances with all three neighbours. If there is a dwarf village in a corner of the island, its inhabitants will never feel safe.

            Task specification

            For a given island description, your task is to decide whether it is possible to form alliances so that all inhabitants of the island will feel safe. In case of a positive answer, your task is also to suggest one viable configuration of alliances. In case of multiple solutions, choose an arbitrary one.

            Input specification

            The first line of the input contains two integers R and C specifying the size of the island. The following R lines encode a description of the island. Each line consists of C space-separated numbers between 0 and 4:

            • 0 means uninhabited area,
            • 1 means an elf village,
            • 2 means a human village,
            • 3 means a dwarf village.
            • 4 means a hobbit village,

            (Note that the number in the input always corresponds to the number of desired alliances for that village.)

            Constraints

            In all test cases assume that 1 \leq R,C \leq 70.

            In test cases worth a total of 55 points we have \min(R,C) \leq 10. Out of these, in test cases worth 15 points R\cdot C \leq 20.

            Another batch of test cases worth 10 points contains maps with only uninhabited areas and human villages. (This batch is not included in the test cases worth 55 points.)

            Output specification

            If there is no solution, output a single line with the string "Impossible!" (quotes for clarity). Otherwise, output one valid map of alliances in the following format.

            Each area should appear in the output as a matrix of 3 \times 3 characters. If the area is uninhabited, the corresponding section of the output will be filled with . (dot) symbols. If the area has a village there should be a a symbol O (uppercase letter O) in the middle representing the village itself, and there should be symbols X (uppercase letter X) representing a configuration of its allies. The rest of the 3\times 3 matrix should be filled with . (dot) symbols.

            For each village type, all possible layouts of alliances are shown in the image below.

            Examples

            input:

            3 4
            2 3 2 0
            3 4 3 0
            2 3 3 1

            output:

            ............
            .OXXOXXO....
            .X..X..X....
            .X..X..X....
            .OXXOXXO....
            .X..X..X....
            .X..X..X....
            .OXXOXXOXXO.
            ............

            input:

            1 2
            2 1

            output:

            Impossible!


            這是 CEOI2010 當(dāng)場(chǎng)唯一會(huì)做的。。。
            題目大意是:告訴一個(gè)70*70的格子里面每個(gè)點(diǎn)的度,每個(gè)格子只能往四周的四個(gè)格子連邊,邊是雙向的,對(duì)于度為2的點(diǎn)所連的兩條邊不能在一條直線上,求出一組方案。
            ============================
            如果沒(méi)有對(duì)度為2的點(diǎn)連邊的限制的話,就把格子黑白染色,建二分圖,相鄰的點(diǎn)連容量為1的邊,黑點(diǎn)連源,白點(diǎn)連匯,容量都為要求的度。流之即可。
            加上對(duì)度為2的點(diǎn)連邊的限制,這樣的方法出現(xiàn)的問(wèn)題在于沒(méi)法處理這個(gè)問(wèn)題了。
            但我們發(fā)現(xiàn),對(duì)于度為2的點(diǎn)的限制可以化為:橫向或者縱向都有且只有一條邊,于是把度為2的點(diǎn)拆成橫的和豎的兩個(gè)點(diǎn)就行了。

            /*
             * $File: alliances.cpp
             * $Date: Thu Jul 15 11:18:14 2010 +0800
             * $Prob: CEOI 2010 The Alliances
             * $Author: Tim
             * $Addr: 
            http://riesky.sk/ceoi2010/problem.php?contest=CEOI%202010%20Day%201&problem=alliances
             
            */

            #include 
            <cstdio>
            #include 
            <cstring>
            #include 
            <cstdlib>

            #define MAXL 71
            #define MAXN (MAXL * MAXL * 2 + 10)
            #define MAXM (MAXN * 4 + MAXN + MAXN) * 2


            #define INFINITE 0x3f3f3f3f
            #define MIN(a, b) ((a) < (b) ? (a) : (b))
            #define OP(x) ((((x) - 1) ^ 1) + 1)

            #define OP_DIR(x) ((x + 2) & 3)

            using namespace std;

            const int fx[] = {010-1};
            const int fy[] = {10-10};
            const int UP    = 3,
                      DOWN    
            = 1,
                      LEFT    
            = 2,
                      RIGHT 
            = 0;


            int map[MAXL + 1][MAXL + 1];
            int n, m;
            void Init()
            {
                scanf(
            "%d%d"&n, &m);
                
            for (int i = 0; i < n; i ++)
                    
            for (int j = 0; j < m; j ++)
                        scanf(
            "%d"&map[i][j]);
            }

            int N = 2, S = 0, T = 1;
            int id[MAXL + 1][MAXL + 1][2];
            int ID(int x, int y, int flag)
            {
                
            if (id[x][y][flag])
                    
            return id[x][y][flag];
                
            return id[x][y][flag] = N ++;
            }

            int edge_id[MAXL + 1][MAXL + 1][4];
            int Count = 0;
            int begin[MAXN + 1], end[MAXM + 1], next[MAXM + 1], c[MAXM + 1];
            void AddEdge(int a, int b, int f)
            {
                Count 
            ++;
                next[Count] 
            = begin[a];
                begin[a] 
            = Count;
                end[Count] 
            = b;
                c[Count] 
            = f;

                Count 
            ++;
                next[Count] 
            = begin[b];
                begin[b] 
            = Count;
                end[Count] 
            = a;
                c[Count] 
            = 0;
            }

            int tot_flow[2];
            void BuildGraph()
            {
                    
            for (int i = 0; i < n; i ++)
                    
            for (int j = 0; j < m; j ++)
                        
            if (map[i][j])
                        {
                            
            if ((i + j) & 1)
                            {
                                
            for (int k = 0; k < 4; k ++)
                                {
                                    
            int x = i + fx[k], y = j + fy[k];
                                    
            if (x >= 0 && x < n && y >= 0 && y < m && map[x][y])
                                    {
                                        AddEdge(ID(i, j, (map[i][j] 
            == 2 ? (k & 1) : 0)), 
                                                ID(x, y, (map[x][y] 
            == 2 ? (k & 1) : 0)),
                                                
            1);
                                        edge_id[i][j][k] 
            = edge_id[x][y][OP_DIR(k)] = Count;
                                    }
                                }
                                
            if (map[i][j] == 2)
                                {
                                    AddEdge(S, ID(i, j, 
            0), 1);
                                    AddEdge(S, ID(i, j, 
            1), 1);
                                }
                                
            else
                                    AddEdge(S, ID(i, j, 
            0), map[i][j]);
                            }
                            
            else
                            {
                                
            if (map[i][j] == 2)
                                {
                                    AddEdge(ID(i, j, 
            0), T, 1);
                                    AddEdge(ID(i, j, 
            1), T, 1);
                                }
                                
            else
                                    AddEdge(ID(i, j, 
            0), T, map[i][j]);
                            }
                            tot_flow[(i 
            + j) & 1+= map[i][j];
                        }
            }
            int cur[MAXN + 1], d[MAXN + 1], pre[MAXN + 1], a[MAXN + 1], cnt[MAXN + 1];
            int sap()
            {
                
            int flow = 0, now, tmp, u;
                a[u 
            = S] = INFINITE;
                cnt[
            0= N;
                memcpy(cur, begin, 
            sizeof(begin[0]) * N);
                
            while (d[S] < N)
                {
                    
            for (now = cur[u]; now; now = next[now])
                        
            if (c[now] && d[u] == d[end[now]] + 1)
                            
            break;
                    
            if (now)
                    {
                        tmp 
            = end[now];
                        pre[tmp] 
            = cur[u] = now;
                        a[tmp] 
            = MIN(a[u], c[now]);
                        
            if ((u = tmp) == T)
                        {
                            flow 
            += (tmp = a[T]);
                            
            do
                            {
                                c[pre[u]] 
            -= tmp;
                                c[OP(pre[u])] 
            += tmp;
                                u 
            = end[OP(pre[u])];
                            }
                            
            while (u != S);
                            a[S] 
            = INFINITE;
                        }
                    }
                    
            else
                    {
                        
            if ((--cnt[d[u]]) == 0)
                            
            break;
                        cur[u] 
            = begin[u], d[u] = N;
                        
            for (now = begin[u]; now; now = next[now])
                            
            if (c[now] && d[u] > d[end[now]] + 1)
                                d[u] 
            = d[end[now]] + 1, cur[u] = now;
                        cnt[d[u]] 
            ++;
                        
            if (u != S)
                            u 
            = end[OP(pre[u])];
                    }
                }
                
            return flow;
            }

            bool ans;
            void Solve()
            {
                BuildGraph();
                ans 
            = true;
                
            if (tot_flow[0!= tot_flow[1])
                    ans 
            = false;
                
            else if (sap() != tot_flow[0])
                    ans 
            = false;
            }

            void Print()
            {
                
            if (!ans)
                    puts(
            "Impossible!");
                
            else
                {
                    
            for (int i = 0; i < n; i ++)
                    {
                        
            for (int j = 0; j < m; j ++)
                        {
                            printf(
            "%c"'.');
                            printf(
            "%c", c[edge_id[i][j][UP]] ? 'X' : '.');
                            printf(
            "%c"'.');
                        }
                        printf(
            "\n");
                        
            for (int j = 0; j < m; j ++)
                        {
                            printf(
            "%c", c[edge_id[i][j][LEFT]] ? 'X' : '.');
                            printf(
            "%c", map[i][j] ? 'O' : '.');
                            printf(
            "%c", c[edge_id[i][j][RIGHT]] ? 'X' : '.');
                        }
                        printf(
            "\n");
                        
            for (int j = 0; j < m; j ++)
                        {
                            printf(
            "%c"'.');
                            printf(
            "%c", c[edge_id[i][j][DOWN]] ? 'X' : '.');
                            printf(
            "%c"'.');
                        }
                        printf(
            "\n");
                    }
                }
            }

            int main()
            {
                freopen(
            "alliances.in""r", stdin);
                freopen(
            "alliances.out""w", stdout);
                Init();
                Solve();
                Print();
                
            return 0;
            }

            posted on 2010-07-15 11:19 TimTopCoder 閱讀(1862) 評(píng)論(1)  編輯 收藏 引用
            評(píng)論:

            只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問(wèn)   Chat2DB   管理


             
            Copyright © TimTopCoder Powered by: 博客園 模板提供:滬江博客
            久久99国产亚洲高清观看首页| 欧美久久综合性欧美| 久久国产精品二国产精品| 久久亚洲精品中文字幕| 久久丫精品国产亚洲av不卡| 香蕉久久夜色精品国产2020| 久久久久精品国产亚洲AV无码| 久久久一本精品99久久精品88| 国产精品成人99久久久久| 无码精品久久一区二区三区| 四虎国产精品成人免费久久| 国产∨亚洲V天堂无码久久久| 久久精品免费观看| 国产午夜精品理论片久久影视| 久久久久亚洲AV无码麻豆| 精品久久久久久国产免费了| 久久无码av三级| 久久本道久久综合伊人| 久久中文字幕无码专区| 国产精品久久久久久福利69堂| 中文精品久久久久人妻| 久久久国产精品网站| 亚洲综合久久综合激情久久| 亚洲乱码精品久久久久..| 精品久久久久久无码中文字幕| 久久久这里有精品中文字幕| 中文字幕精品无码久久久久久3D日动漫| 亚洲精品午夜国产va久久| 亚洲色大成网站www久久九| 亚洲国产精品无码久久九九| 久久无码高潮喷水| 99国产精品久久| 欧美午夜精品久久久久久浪潮| 久久久亚洲裙底偷窥综合| 狠狠色丁香婷综合久久| 久久伊人中文无码| 久久久无码精品亚洲日韩蜜臀浪潮 | 精品国产91久久久久久久| 久久最新免费视频| 亚洲精品无码久久久久去q| 亚洲午夜久久影院|