首页 > 代码库 > Uva 10336 Rank the Languages

Uva 10336 Rank the Languages

 1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 void Dfs(int x,int y); 5 char MapString[1000][1000]={0};//要判断的“地图” 6 bool vis[1000][1000]={0};//节点是否本访问过, 7 int main() 8 { 9     int h,w;//h:height;w:width10     int line;11     int MaxChar;//”语言”被使用的“国家”数;12 13     while(cin>>line){14         for(int m=0; m < line;m++)15         {16             memset( vis, 0, sizeof(vis) );17             int letter[29]={0}; //“语言”统计18             MaxChar=0;19             //以上应在此循环内初始化20             cin >> h >>w;21             //输入部分22             for(int i = 1;i<=h;i++){23                 for(int j = 1;j<=w;j++){24                     cin>>MapString[i][j];25                 }26             }27             for(int j = 1;j <= h;j++){28                 for(int k = 1;k <= w;k++){29                     if(vis[j][k] != 1){30                         MaxChar = max(++letter[MapString[j][k]-a],MaxChar);31                         Dfs(j,k);32                     }33                 }34             }35             cout<<"World #"<<m+1<<endl;36             for( int j = MaxChar; j >= 1 ; j-- ){37                 for( int k = 0 ; k < 26 ; k++ ){38                     if( letter[k] == j ){39                         cout<<(char)(a+ k)<<": "<<j<<endl;40                     }41                 }42 43             }44         }45     }46     return 0;47 }48 void Dfs(int x,int y)49 {50     vis[x][y] = 1;51     if( (MapString[x+1][y] == MapString[x][y]) && (vis[x+1][y] !=1) )Dfs(x+1,y);52     if( (MapString[x-1][y] == MapString[x][y]) && (vis[x-1][y] !=1) )Dfs(x-1,y);53     if( (MapString[x][y+1] == MapString[x][y]) && (vis[x][y+1] !=1) )Dfs(x,y+1);54     if( (MapString[x][y-1] == MapString[x][y]) && (vis[x][y-1] !=1) )Dfs(x,y-1);55 }

算法:dfs;

思想:递归。

Uva 10336 Rank the Languages