牛客小白月赛104——D.小红开锁

一、题目

样例：

2
OXXX
OOOO
OXOO
OOOO

3

说明：

对内层操作2次，对外层操作1次即可开锁。

二、思路

        首先我们会想到我们肯定是要一层一层单独处理的，并且我们可以找到X串应该在的位置，我们以末尾为基准，如果用开头比末尾复杂，如果你想要用开头也可以，这里以末尾为例子，我们去找到此时的x串的末尾的位置，因为如果想要开锁其实是有四个方式，在左上角，右上角，右下角，左下角拼对应的图案，算移动的位置其实就是用应该在的位置-现在的位置，由于可能得到负数，于是用减法的同余原理(应该在的位置-现在的位置+该层的总长)%该层的总长得到最后答案.

三、具体代码

！！！我的代码里也有相应的注释

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int main(void){
	cin.tie(0);
	cout.tie(0);
	int n;
	char s[220][220];
	vector<char> a;	//用来记录每一层的图案 
	int ans[4];	//这个表示四个位置
	//在最里面那层我们知道一共有四个格子，
	//我们可以在任意一个角拼成题目要求的的图案
	cin>>n;
	for(int i=1;i<=2*n;i++){
		for(int j=1;j<=2*n;j++){
			cin>>s[i][j];
		}
	}
	for(int i=1;i<=n;i++){	//这代表每一层
		a.clear(); 
		//从上面边界开始记录 
		//为什么是n*2+1-i——你可以画图发现每一层的边界位置
		//方向   	x     			y
		//上     	i     		i~2*n-i+1
		//右   	i+1~2*n-i+1      2*n-i+1
		//下      2*n-i+1        2*n-i~i
		//左     2*n-i~i+1          i  
		
		//上边界
		for(int y=i;y<=2*n-i+1;y++){
			a.push_back(s[i][y]);
		} 
		//右边界
		for(int x=i+1;x<=2*n-i+1;x++){
			a.push_back(s[x][2*n-i+1]);
		} 
		//下边界
		for(int y=2*n-i;y>=i;y--){
			a.push_back(s[2*n-i+1][y]);
		} 
		//左边界
		for(int x=2*n-i;x>=i+1;x--){
			a.push_back(s[x][i]);
		}
		
		//计算当前层的总方块数
		int sum=((n-i+1)*2-1)*4;
		int end=0;	//X串的终止位置,
		//下面的for判断不了是不是在第一个位置，
		//所以初始化为第一个位置0 
		for(int j=0;j<sum;j++){
			if(a[j]=='X'&&a[j+1]=='O'){
				end=j+1;
				break;
			}
		} 	
		int k=(sum/4)/2+1;	//表示x串应该回归的位置 
		//根据end的位置来确定 
		ans[0]+=(k-end+sum)%sum;	//x串在左上角 
		ans[1]+=(k+sum/4-end+sum)%sum;	//x串在右上角 
		ans[2]+=(k+2*sum/4-end+sum)%sum;	//x串在右下角 
		ans[3]+=(k+3*sum/4-end+sum)%sum;	//x串在左下角 
	}
	sort(ans,ans+4);
	//取最小的结果 
	cout<<ans[0]<<endl; 
	return 0;
}