专栏文章

题解：P13390 [GCJ 2010 #1A] Rotate

wwuyikai2011
P13390题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mios090p
此快照首次捕获于
2025/12/03 00:12
3 个月前
此快照最后确认于
2025/12/03 00:12
3 个月前
查看原文
很常规的一道模拟+dfs。
只要捋清几个步骤就行了：
①将棋盘顺时针旋转90度；
②将旋转后的棋盘中的棋子按重力下落；
③对其中每个棋子dfs判断与其相连棋子个数。

①：将棋盘旋转90度

这是题目中的例子：
CPP
.......
.......
.......
...R...
...BB..
..BRB..
.RRBR..
分别写出它们的下标及旋转后对应的下标：
CPP
c[1][1]->c[1][7]
c[1][2]->c[2][7]
c[1][3]->c[3][7]
c[2][2]->c[2][6]
c[2][3]->c[3][6];
……
由此可以很容易地得出：
c[i][j]旋转90度->c'[j][n-i+1]
这样一来，第一步就解决了：
CPP
cin>>n>>k;
for(int i=1;i<=n;i++){
	for(int j=1;j<=n;j++){
		cin>>c[i][j];//c:原数组 d:旋转90度后的数组
	}
}
for(int i=1;i<=n;i++){
	for(int j=1;j<=n;j++){
		d[j][n-i+1]=c[i][j];
	}
}

②：模拟重力使棋子下落

这步也很简单，只要枚举每一列，判断每个棋子是这一列中从下往上数的第几颗棋子，再存入相应位置就行了。
CPP
for(int i=1;i<=n;i++){
	for(int j=1;j<=n;j++){
		e[i][j]='.';
	}
}
int ci=0;//ci:下往上数的第几颗棋子 e:模拟完重力后的数组
for(int j=1;j<=n;j++,ci=0){//ci一定要清零
	for(int i=n;i>=1;i--){
		if(d[i][j]!='.'){
			e[n-ci][j]=d[i][j];
			ci++;
		}
	}
}

③：dfs搜索每颗棋子

这里只要注意：从上往下枚举每个不是"."的位置进行dfs,每次只往右/下/左下/右下遍历，不需要记录每颗棋子是否已遍历。
AC代码：
CPP
#include<iostream>
#include<cstring>
using namespace std;
int T,m,n,k;
char c[110][110];
char d[110][110];
char e[110][110];
bool vis[110][110];
int di[4][2]={{1,0},{0,1},{1,1},{-1,1}};
bool fB,fR;
void dfs(int x,int y,int cnt,int dir){
	if(e[x][y]=='B'&&fB) return ;
	if(e[x][y]=='R'&&fR) return ;
	if(cnt==k){
		if(e[x][y]=='R') fR=1;
		if(e[x][y]=='B') fB=1;
		
	}
	int dx=x+di[dir][0],dy=y+di[dir][1];
	if(dx>=1&&dx<=n&&dy>=1&&dy<=n){
		if(e[dx][dy]==e[x][y]){
			dfs(dx,dy,cnt+1,dir);
		}
	}
}
int main(){
	cin>>T;
	m=T;
	while(T--){
		fR=0,fB=0;//多测要清零
		cin>>n>>k;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				cin>>c[i][j];
			}
		}
    //旋转90度
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				d[j][n-i+1]=c[i][j];
				e[i][j]='.';
			}
		}
    //模拟重力下落
		int ci=0;
		for(int j=1;j<=n;j++,ci=0){
			for(int i=n;i>=1;i--){
				if(d[i][j]!='.'){
					e[n-ci][j]=d[i][j];
					ci++;
				}
			}
		}
    //dfs每颗棋子
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(e[i][j]!='.'){
					if(e[i][j]=='B'&&fB) continue;
					if(e[i][j]=='R'&&fR) continue;
					dfs(i,j,1,0);
					if(e[i][j]=='B'&&fB) continue;
					if(e[i][j]=='R'&&fR) continue;
					dfs(i,j,1,1);
					if(e[i][j]=='B'&&fB) continue;
					if(e[i][j]=='R'&&fR) continue;
					dfs(i,j,1,2);
					if(e[i][j]=='B'&&fB) continue;
					if(e[i][j]=='R'&&fR) continue;
					dfs(i,j,1,3);
				}
			}
		}
		cout<<"Case #"<<m-T<<": ";
		if(fB&&fR) cout<<"Both";
		else if(fB) cout<<"Blue";
		else if(fR) cout<<"Red";
		else cout<<"Neither";
		cout<<endl;
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...