uva705一次AC

这题读完想了一会,没有什么思路,不知道如何处理‘\’和‘/’,因为它们是“墙”,但是这墙是具有方向性的;而且没有路,输入全部由“墙”组成,与以往做过的图找路径的题目有很大的不同,一时没有办法。

后来看了网上的思路,觉得非常好。做法就是把原图放大2倍或3倍。放大2倍是指用2*2的0-1矩阵表示‘\’或‘/’

具体为‘\’表示成1 0   ‘/‘表示成 0 1

                        0 1                1 0

同理,放大三倍的表示方法为:

‘\’表示为1 0 0  ‘/’表示为0 0 1

              0 1 0              0 1 0

              0 0 1              1 0 0

这样做的好处是放大了墙,从而产生了路。0表示路,1表示墙,处理起来就方便多了。放大2倍每步要考虑8个方向,放大3倍考虑4个方向即可。

附上AC代码,一次AC!

#include<iostream>
#include<cstring>
using namespace std;

int w,h,circles,maxroad,map[250][250];
int dr[4]={-1,0,1,0};
int dc[4]={0,1,0,-1};
bool ok=1,visit[250][250];
void fill(int type,int row,int column){
	if (type==1){
		map[row][column]=1;map[row][column+1]=0;map[row][column+2]=0;
		map[row+1][column]=0;map[row+1][column+1]=1;map[row+1][column+2]=0;
		map[row+2][column]=0;map[row+2][column+1]=0;map[row+2][column+2]=1;
	}
	else{
		map[row][column]=0;map[row][column+1]=0;map[row][column+2]=1;
		map[row+1][column]=0;map[row+1][column+1]=1;map[row+1][column+2]=0;
		map[row+2][column]=1;map[row+2][column+1]=0;map[row+2][column+2]=0;
	}
}
int dfs(int row,int column,int &steps){
	int nr,nc;
	for (int i=0;i<4;i++){
		nr=row+dr[i];
		nc=column+dc[i];
		if (nr<0||nr>=3*h||nc<0||nc>=3*w||visit[nr][nc]==-1) {
			ok=0;
			visit[row][column]=-1;
		}
		else if (visit[nr][nc]==0&&map[nr][nc]==0) {
			visit[nr][nc]=1;
			steps++;
			dfs(nr,nc,steps);
		}
	}
	return steps;

}
void init()
{
	circles=0;
	maxroad=0;
	ok=1;
	memset(visit,0,sizeof(visit));
}
int main(){
	int col=0;
	while(cin>>w>>h&&w)
	{
		init();
		col++;
		for (int i=0;i<h;i++)
		{
			for (int j=0;j<w;j++){
				char c;cin>>c;
				if (c==‘\\‘) fill(1,3*i,3*j);
				else if (c==‘/‘) fill(2,3*i,3*j);
				else cout<<"wrong input!"<<endl;

			}
		}
		for (int i=0;i<3*h;i++){
			for (int j=0;j<3*w;j++){
				int count=1;
				if(visit[i][j]==0&&map[i][j]==0) 
					{
						ok=1;
						visit[i][j]=1;
						dfs(i,j,count);
						if (ok) 
						{
							circles++;
							if (count>maxroad) maxroad=count;
						}
					}
				
			}
		}
		cout<<"Maze #"<<col<<":"<<endl;
		if (circles>0)	cout<<circles<<" Cycles; the longest has length "<<maxroad/3<<"."<<endl<<endl;
		else cout<<"There are no cycles."<<endl<<endl;
		
	}
	return 0;
}



uva705一次AC

上一篇:最小树形图模版


下一篇:用 SpriteKit 做一个逃逸游戏 (2)