首页 > 代码库 > Uva 705 Slash Maze
Uva 705 Slash Maze
题目的意思是在图中寻找可以构成的回路数，及最大回路经过的格子数。
题目不是简单的横竖的格子，而是斜的，这样就不太容易了。后来上网看别人的思路，把图放大三倍，就豁然开朗了。
解题报告链接：http://blog.csdn.net/sio__five/article/details/18910097
代码我修改了一下，留着自己以后慢慢学习。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 6 int length, width, grid, Max; 7 int g[300][300], isVis[300][300]; 8 int Move[4][2] = {{0, -1},{0, 1} , {-1, 0} ,{1, 0}}; 9 10 bool IsIn(int x, int y);11 void NoEffectFill(int x, int y);12 void SetBound();13 void Dfs(int x, int y);14 15 int main ()16 {17 // freopen("D:\\acm.txt","r",stdin);18 int No = 1,cycleNum;19 while(cin>>length>>width,(length||width)){20 width = width * 3, length = length * 3;//将图放大三倍21 memset(g,0,sizeof(g));22 memset(isVis, 0,sizeof(isVis));23 Max = 0;24 cycleNum = 0;25 for (int i = 1; i < width; i += 3){26 for (int j = 1; j < length; j += 3){27 char ch;28 cin>>ch;29 if (ch == ‘\\‘)30 g[i - 1][j - 1] = g[i][j] = g[i + 1][j + 1] = 1;31 else32 g[i - 1][j + 1] = g[i][j] = g[i + 1][j - 1] = 1;33 }34 }35 SetBound();36 for (int i = 0; i < width; i++){37 for (int j = 0; j < length; j++){38 if (!g[i][j] && !isVis[i][j]){39 grid = 0;40 Dfs(i, j);41 if (grid >= 12) cycleNum++;//小格子大于12即大格子大于4，构成一个回路42 if (grid > Max) Max = grid;//记录最大格子数目43 }44 }45 }46 printf("Maze #%d:\n", No++);47 if(cycleNum != 0)48 printf("%d Cycles; the longest has length %d.\n", cycleNum, Max / 3);49 else50 printf("There are no cycles.\n");51 printf("\n");52 }53 return 0;54 }55 bool IsIn(int x, int y)56 {57 return (x >= 0 && x < width && y >= 0 && y < length);58 }59 void NoEffectFill(int x, int y)60 {61 int nextX, nextY, i;62 isVis[x][y] = 1, g[x][y] = 2;63 for (i = 0; i < 4; i++){//将外围的空格填充掉64 nextX = x + Move[i][0];65 nextY = y + Move[i][1];66 if (IsIn(nextX, nextY) && !isVis[nextX][nextY] && !g[nextX][nextY])67 NoEffectFill(nextX, nextY);68 }69 }70 void SetBound()71 {72 for (int i = 0; i < width; i++){73 if (!g[i][0] && !isVis[i][0]) 74 NoEffectFill(i, 0);//设置图的外围边界75 if (!g[i][length - 1] && !isVis[i][length - 1]) 76 NoEffectFill(i, length - 1);77 }78 for (int j = 0; j < length; j++){79 if (!g[0][j] && !isVis[0][j])80 NoEffectFill(0, j);//设置图的外围边界81 if (!g[width - 1][j] && !isVis[width - 1][j]) 82 NoEffectFill(width - 1, j);83 }84 }85 void Dfs(int x, int y)//递归寻找格子86 {87 int nextX, nextY;88 isVis[x][y] = 1;89 grid++;90 for (int i = 0; i < 4; i++){91 nextX = x + Move[i][0];92 nextY = y + Move[i][1];93 if (IsIn(nextX, nextY) && !isVis[nextX][nextY] && !g[nextX][nextY])94 Dfs(nextX, nextY);95 }96 }
Uva 705 Slash Maze
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。