hdu-1198 Farm Irrigation---并查集+模拟（附测试数据）

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1198

题目大意：

有如上图11种土地块，块中的绿色线条为土地块中修好的水渠，现在一片土地由上述的各种土地块组成，需要浇水，问需要打多少口井。

例如下面这个土地块

ADC

FJK
IHE

then the water pipes are distributed like

解题思路：

首先模拟A-K的四个不同的方向，用了一个数组表示从A-K的四个方向是否有水管

然后枚举每个点的四个方向上可到达的地方，如果连通就合并并查集，最后根节点的数目就是连通块的数目（DFS也可以做，判断连通块即可）

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn =  + ;

 int p[maxn];

 char Map[][];

 int dir[][] = {,-,-,,,,,};//分别是左(0)，上(1)，右(2)，下(3)

 int G[][]={

     ,,,,

     ,,,,

     ,,,,

     ,,,,

     ,,,,

     ,,,,

     ,,,,

     ,,,,

     ,,,,

     ,,,,

     ,,,,

 };

 void init()

 {

     for(int i = ; i < maxn; i++)p[i] = i;

 }

 int Find(int x)

 {

     return x == p[x] ? x : p[x] = Find(p[x]);

 }

 void Union(int x, int y)

 {

     x = Find(x);

     y = Find(y);

     if(x != y)

     {

         p[x] = y;

     }

 }

 int main()

 {

     int n, m;

     freopen("out.txt", "w", stdout);

     while(cin >> n >> m && ( n + m > ))

     {

         init();

         for(int i = ; i < n; i++)

         {

             cin >> Map[i];

         }

         for(int i = ; i < n; i++)

         {

             for(int j = ; j < m; j++)

             {

                 int c = Map[i][j] - 'A';

                 for(int k = ; k < ; k++)//枚举四个方向

                 {

                     if(!G[c][k])continue;//判断该方向是否存在水管

                     int x = i + dir[k][];

                     int y = j + dir[k][];

                     if(x <  || x >= n || y <  || y >= m)continue;

                     int d = Map[x][y] - 'A';

                     if(!G[d][(k + ) % ])continue;//这里是判断（x，y）处是否有和k方向相对的方向的水管

                     Union(i * m + j, x * m + y);//这里是编号i*m+j，一开始写错成i*n+j

                 }

             }

         }

         int flag = ;

         for(int i = ; i < n * m; i++)

         {

             if(p[i] == i)flag++;//根节点的数目也就是连通块的数目

         }

         cout<<flag<<endl;

     }

     return ;

 }

测试数据：

 JBHFFKBAHHFIGHDHJ

 CHHIKGHIFGHCBJKKC

 EJHFEHFGHAFAFEFBD

 KGAAGHIHKDFCKJKDK

 BBGIFFCEGGFGFABEF

 GFHEAIEEADDFIEHIC

 AIHHEBFCHJAKDIEBG

 CJCDGFJFHEGBKHJKH

 AHCAAKHKBBKJJJGGB

 HJJHFIBDAKEHEFHGD

 CJJICAAJJEJIHJDEK

 FKKIKJBKGKKJEEFIC

 IIGJJIDFHKFDCKJDK

 KBKFHKHDCJIDJBFDF

 KBHBFJEIFFKFGCAIG

 CKJEBHICKEGABEIHC

 EJECEHIDDKJAIDEAG

 KGIJAAJDHABDEIGCF

 FIFJECCEKDAAKCACG

 HIAFBCCDFIIKCAJBB

 AAKGGBBDHAHJIIIEB

 FCBIFKACGFEHIECII

 IFBEKFGKFGADIHICH

 HIJHFFEIHDGKEAKIE

 GHCHDKBIECFJEFKHA

 KHCHCDAGJDJEAKJJD

 DKIKAJCCACJBCEDKD

 IGHKIGDHBBFGJGKJK

 DFGDIAJJHIIGCIFCC

 AIGJJKKJJDJEEJFAE

 CIEFBGGCBDFAFFEBK

 EEAIDJEEEBDGKCFBG

 DFJFACCJIGJHBDAGK

 CEJFDBHCGDGHADAKB

 IAJBKKHDEEAIJICBA

 CBKFKEBJFJGJBDECH

 EIFHJCBCBJKKIDDJA

 GIABAIIDHEBIHGIDF

 FFHFCFJAIFFEIJEJG

 KAFFDFEIECBEFKCEK

 ICKGEAFCJFIEHBHCG

 GKDKJKAGKAICDIJBGACJ

 AHCBFGDCEDKGEAFKIBAA

 JHCBAJFFEIFFFCKEHJJB

 IEHDIDJCHGIBKGFDJGJC

 IAGEBDGCJBKAIHGCBAHE

 EGHFJIKEHCEFFFGJBBEF

 DKDFABABFFADDKJEJJGB

 CEIKJHCDKGIAFACFJDKG

 JAGAAIIDCKKFCCJBCCAF

 AFEGEAGEKAHBCJDII

 KAGCGJBEDJGIADCGA

 CFGECKBGJHIBIBGKD

 ICAFDEBHDBDFEDGGK

 HDIJCJFCHJHFEGHIE

 DBKJFFHBGFGGAEHED

 JGGECHJGCJHAGHGDK

 EKHBEHDGADFKJKECD

 DFKFIIFJFKJKDBDHI

 HAFKCCDFDIKCJBBGA

 GFHFFFEKHCKABAJEE

 HKECDKCACJKACHGAK

 DHJEKABBKGIGFCJAC

 JIFHJJBGDAFFGAJII

 CCHCADJFHECGCBIDE

 KKEKJBABDABJDBACH

 CCEKGGIFFCFJEAKJB

 ADIKJAFEBKCJIHFFE

 KKGCBJCJDIDBGFDCF

 JFBFAAJFHBABCDHAF

 AIHFBJDIFGKIAGIIG

 GABJIFFFKEFIABBGH

 BFKEAEEHJJJEFBJFA

 FJHIHDCDHIJEBHJIF

 IECKGJFBJFBDFBBECKEKGGGEKAA

 FCHKJFDEAHGFIHHGIJJGCBEEEHG

 GIEADGFJBIDIEKBDIGAJAFFGFEA

 GCDIBKEJGFIJHKHABAJAHBDDBIK

 FBCFCEGEDIBJIJDIKAGEBCHBCIH

 KAEIKCBCEGGGHBIICFBAEIJFDEC

 FDGEFKIHHGEHIDDKDBEEFCBFGKI

 HDFAJBDDGHFFAHBJAHKAJCEECBF

 BDDGFCFKCCIACKGEDBFJBDFDDFA

 ABECCDFDAKDACBBBJBEGEABFIIK

 BHHKHAGDKGDFDKGEEFEFICEGBHE

 HFFKFCEFCDDFADAAAFFBCJIKKJJ

 IEJGAHEBKIKBIFHBFBECJEHJHEC

 JDHHHDECGCIJDFCDFGHCDJECCKG

 DFEEGCJKHHCCCFEKKEIEEJIAKEA

 BDIGGFKCHDKJAHCCIGBFIKAAIEC

 KBECAFKFJBICDIEKEBIAGDCKFAH

 FCJJEHCJCKFHIHFEFKCEJGDDIEH

 BACDHJDAAIDABGFDKGEEBKKEKKJ

 JHFHCGCBDBFIIFFAHFAFJGGAIFB

 DHEDBHBFCFGEKGGDEFJFAHKDBBD

 EGDDJIFEHIBDAIBIEHHFKDEIDAB

 BGCCKBFBCBKKIFCAIJIECHICHEB

 KCFKGABEKEFJFGBKGEAEFCJFIGH

 BHFCEEJKBKGDBBJEEHKBFHDBGFF

 CFHEDFEDJFKJECIAKBIEJAKHABD

 DFEAFCEFEBHBEAKIDFDKEJAICCD

 EJGDIHDHIBBEDFHKJEIFCCDHACC

 GJGAIDBJDCGKKKHBAIDAAEACEDA

 JCHFFAHCKGFFBCIFKGCAJAJKBBH

 GHACAHIDBBIBCAAEHJBHGJGGIHI

 KECKGDJGAIDIIDBJJFDKJBIHIFA

 EGJKFCJAHHIIBJHIADJBAHHCDAH

 AGDKCHCCECHHCAKCACHFJHIFJEA

 GJAGCCED

 DAKIBIAH

 FAEFHFKA

 KCCEDIIJ

 ECAIDGJE

 JJBAJDFI

 HFIBJEJG

 KEIGFDIC

 CBGFFCKK

 ICAGAFGH

 HCEKFBBE

 DFDDACDC

 BEADDBKF

 CAKBCEID

 IHKJFIHD

 KBIHCCHK

 BKBDBCGG

 EHFKJKJC

 IHEAKAKH

 DDHKKFBD

 BHGKBCEI

 EIJEICIH

 HFHGGKJF

 KJBJCHKC

 ADBEGCDH

 KIADDADJ

 KJBEEBII

 JFHKGBHK

 CHJGKJJB

 GEDECEED

 BCJDIGBK

 DIGDHFIE

 ADIEFJGH

 BAKACBDH

 HBDBEJGD

 BJICHIAH

 ADIJEKID

 HBEAHCBA

 HIHCAKEK

 CJHKCGBC

 BKEEEKCJ

 AGEEBDBKHKECEFBBCDIBHDDD

 IGFGGKFEFHBFHCAHIBJEEDBG

 BAJHKKEFEDKCIJIBECDBDBKH

 JHHDCHJDHDIGHJKFHEHIGHKA

 IEHCGKGJFFBEJDCHGEDIBDFH

 CDHHBAGABFBDAFCJIBJDDKCC

 CIJIFHFGHCCEECBGHEBCGDCI

 FBCFIIJFHBJFKGJHAKBHGJIK

 DGEFKHGJJCEFFKHKGGBCKIIH

 IFGJCDGCDHIHBEDCJECHJBBJ

 KKBFAGDHJEEGHFIDKFBBBB

 BKIIBJIKJFJHJJDBDBJIHI

 HCBGEDAEHHFCFJJAIDEKIG

 JEDFBDGDHKDBIHEJCCFAKJ

 CFJAAFIEKGKHCCAIHEBKBH

 CBCEIEHBGIAKHAFHEAAHKK

 ECDHIEHCBGAFIECFHCEBFG

 BGBBFJJIJKKDCCKGBJJABH

 AGBHCKJBDHBIBBHHIGGEGC

 HJKDFKAKKHGJKKEHJCIGIB

 DAFAEEFGDGKBFHJKHEIBBK

 FBGBEEDDAEHHIIIHHFHBKJ

 IJCEDACCJAFEGEEFHBKIEH

 ADKEFBAFDDDCACIAIJCEIB

 HBKGDDBBFIGHKEDGHECGJI

 FDBACAADDKADFCFIHAIDKH

 FBIFJBDCJGJAIBBKFBDFJH

 KAEKBAJBGBAHDEFHBBHKJI

 HJGJBJHBKBJHAFBACEBJDF

 FBDBDHKDJBEGJIJHKDJFAHCKCBEDDDICECG

 DKKAGKFHKIJCAHBDFDFBDKDEIEHFDIEABCG

 GGHKFIFFKGEAKEBKHDFHIADCHGABEDAHJIE

 KDHJFKFEKHIAJKJIFJKBGFECGJFHCEIECBB

 BAGGKCKGBBKIECEIBCCAGEFIHKICKDHFKCG

 FJICKFJGDAAAGCGJEIIHFCIHDJJCBCHIFAH

 CEKGCHKFJAECKCIAGAEGGAKCHBBJCIKBCDD

 DBIGHDKCFJIKEIBKAKAKCEGDCHJEBCHAJIA

 HKIDEIDDKCGHJAAJDBFEIJFDFEAEIIFHFEB

 DAFIGJGAKECEGFGGCIGGEFCFIFAAKGDJDGA

 ABIJEBEEJAHHKCKDFJFCFDGBADIJJBKGKCI

 JIKIBJIHBDFDHEFCFFGHJCDDBIEDGDKGBIA

 KDFBGBBHCFJEFHCGJIFBHCADKCDJIDJFGCE

 ABAGDCHEAJJEDFEIFICCDKFJGKJGGIGJDJB

 BEGHHIHGCEDEBBJKHHEJEKDFFHJKIEAIAAE

 DGFDICAEEICGJHCJEAACFHFGKFEBBAGEAHA

 IKIDCIJJIEIKBCCFFFHJCJBDADHHJHCGJAJ

 AFKHJKKKAFEFFAHJKKCCGJGIKKHKIGGADCF

 JGCABJGJEAGHIBHGBGDCAFGGBJFDDAAHJCA

 JHBCKGIHIAJFBFEBKFGGKAAKHEDGABHEKGF

 HEIEIDGJJDAIHDAGGCKCEDFEKIGHCGFBFBK

 JAGKDHFDBCJKCDKBHAIHBKDJDBKDCHDKDEK

 DBJAFIABDDKECJHGEAKJAJKCKDFIJAAEGKB

 ABGBHGKHAJGBAGFEIJBIKJBHCJGGEADCIFB

 CIJFGAGIDKADJBHDBJJGKGBKGAHBDHIHBAK

 EIBCHHEAEJCFKBGFJJIAKHGAEAGBGEGCGGC

 HDGKDBKBHJFIJCJFKKKIBGBIIFDBFJAIKIB

 IDHGAFGDKICBEECHBKKKGDIBHDGAKBEFFCH

 EBGHAJFJAEAHIEHFJHBIKJKJDJDHGAHBKCC

 KDIJAAAFKAKDJJEHFIGKIHJHFCKHKGGEGDF

 GKEKHFDEEFCHKFBEGIFKGFICDFDBGIDBGBE

 JEDKJKHFGHDIBJBKDHDICJCFIHKDFFCHBGA

 DDHKGKFKBEBACKCJHADJFHHKBHJBFHFFHGA

 IHBGKHAEJKCDJDDEEHGHCCABIBIKG

 KGJIBGACAJCCGKJHBJGBFBBDEBDKI

 ICAHBGBBEFKFEEKACBIFIFGHICHCA

 DHKCBJGFEFJHAFKKEKKBGJIGCGDEB

 AFFDEKFBKBDIGGKAGIHIBGGKDABBK

 JFIACGCFDIJHHGIDJKCFBEEEKAEIH

 GIDICCGFFDFHIFBBDJECFHKGIHGCE

 CEBABFIJDCIFHFKBAIJJGGCFKBEKC

 FHIEKJKICFJEIKEGKIBGEAJADIHIF

 EBKBHIIFEBBAGIBHIAJKBFJDDCFEG

 CADAICKIJBHHEFIKIJHDEBBAEFGJI

 JGEBHCDGIJDIKFCJBIHFHCFKBCGJK

 DFJKCFABBIFFECHHGCKIHHKFJHBDJ

 ACGCHJDKJGJFIGKFBIGKDBDBCKCBK

 GKJHCIJGFHDHJAGACHFIFIAJBFGFK

 FGJEAFIGBHGFBJBIJFJAHDDGCHIBK

 FIFIEGHJIKFHJACAJKKCEFIGDHJGE

 FBHDFKGDJJIKHKDCIJDIBFJHCFJAK

 GGBDICEDIAEBFJIIIDHBKKBHHFKEB

 JACKFBIHDCIGDBEGCDJFCKBDECACF

 KHFIJBHKCCFCKECAJBKHHJACKEIGD

 KFEAFBEIJEJHGGDAEIDJHAAHJEDFK

 IGJEIAIJJKDKDCDDADJEGDCGCFDGE

 GCIFJKCKHICIJKADADEGGFDCJFCDI

 CEAHIBIDAEIACICKKHBJFGJGCECJE

 HBKGFGCABDABCEKJCICFJDDJBJACI

 JHGDJAKCHHEADHEJAJHABDCDJHBJI

 EHJKCIEKACKJDJCAABGEAFJDKAAGC

 DDKKJHDDDGJIADDDGEKEEJAJDEGDD

 KAFKGFKCFABFGCHBGEAHBCBBDHKBBDHIJEJIIACHDCBICDAH

 AHIEDHBIEGIIKBAEHJJFJDBGBIKKHBAFDADCAIEEJFGCAKEK

 KCDDJCDEBGHGDCFFKIIEBEJHDDAHCIDGADGHAAIFDHACJCFH

 DFJHDJCEAGGEAICHEHGDKFCIGKDKEFCFFFIJKHGGECGIKKKA

 AJACFFJJFCDGDIGAGCHJGKAHGEFIECACKIBGAAIBHDHIEGAF

 GJIBDFIBHAGAFIDGKFGHCJAJICDJIBJEAJDAEBKGCFIJDEGC

 HBABAJCHGFKGIBGBIEJDEHJAKFFHFBBHHHAIJIEDGKKBDKIJ

 KIKJDKBIGCJAAIJHDAGFBEEKEFKGDHJDABCIGGBKDEFJDCKB

 FDFJADGHAFFEFKIDKJBGIEHDCDGKJBICHCIAKDGBAKGCFKDI

 IHJHAKDHGEJHHGGFEIHIFBEGHAJKGAEJDCAKHJKABJKGBBKB

 GHBAHCIFFJGFBCACABIDFKGHHDJDKGEEIAIKKEGFHGFEBBCD

 HIBADGAAHJAIAGGKCDHIBAAEKKCAHGEDDKEHHFFJGIJAHICE

 CFGCAIBCDDECDJHKCJGJDKCBHDAHIKDJKAJJDADCFEKJKAFA

 GCDEFHEJAIAJDGFDDADJGEIAJCKBICDGABKEDAFFGBIIHDBE

 AIFDACKBJHBEEGIJDFBCJEKFBHICGGBFJCHIBJCIJIJCHAEF

 KBEFKDCIEEDEBKIIBGDHGJFHGKCHJGCJFIGIDACBIGCJHKEK

 CIICHEEIBGHHFCICKGECHJFBFKHBAKEGBCKCHKHKCKFDHJDG

 GIKABBAIKJJDEECKBEECEHBHECDEGDICCGAGCCHCJAADBIFK

答案：

巴特西

hdu-1198 Farm Irrigation---并查集+模拟（附测试数据）

最新文章

热门文章