LiaN

是一只废物捏

0%

【题解】递推（几道翻转类题目）

发表于 更新于 分类于 本文字数： 3.8k 阅读时长 ≈ 3 分钟

AcWing 116 飞行员兄弟

题目链接

大意:

  • 4 x 4 翻转一个元素的话，顺带着所在行和列全跟着翻转；求全部翻转过来的步数和步骤

思路

  • 如果枚举的话，2<<16次，复杂度还能够接受，可以枚举
  • 枚举每个操作opt，每个操作opt的值转换成16位二进制，
    • 对于每个opt，要移位16次，每次右移取最低位 ,当==1表示翻转
    • 注意翻转i行j列的时候，(i,j)被翻转了两次，记得恢复
    • 储存符合条件的操作的位置，用vector存

笔记

  • vector

    1
    2
    3
    4
    5
    定义： vector<元素类型> 名称；例如： vector<PII> vec;
    翻转： reverse(vec.begin(),vec.end());
    大小： vec.size();
    清空： vec.clear();
    插入： vec.push_back(pi);

  • for区间遍历 (C++11)

    1
    2
    3
    for(auto i:vec){
        cout<<i.x<<' '<<i.y<<endl;
    }

  • pair

    1
    2
    3
    4
    #define x first
    #define y second 方便
    typedef pair<int, int> PII;
    PII pi; pi.first, pi.second

  • memcpy

    1
    2
    void *memcpy(void *str1, const void *str2, size_t n)
    str1：目的 str2：源 n：字节数

  • 二进制数i的第k位是否==1

    1
    i>>k&1

简洁版代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
#include<vector>
using namespace std;

const int N=5;
char ch[N][N],backup[N][N]; 
typedef pair<int,int> PII;
vector<PII> vec; 

void turn(int i,int j){
	for(int k=1;k<=4;k++){
		if(backup[i][k]=='+') backup[i][k]='-';
		else backup[i][k]='+';
		
		if(backup[k][j]=='+') backup[k][j]='-';
		else backup[k][j]='+';
	}
	if(backup[i][j]=='+') backup[i][j]='-';
	else backup[i][j]='+';
}

int main(){
	for(int i=1;i<=4;i++)
		for(int j=1;j<=4;j++)
			cin>>ch[i][j];
	for(int opt=0;opt<(2<<16);opt++){
		int step=0;
		memcpy(backup,ch,sizeof ch);
	 	for(int i=0;i<16;i++){
	 		if(opt>>i&1){
				int row=(16-i-1)/4+1;
				int col= 4-i%4;
				turn(row,col);
	 			step++;
	 			PII pi; pi.first=row;pi.second=col;
	 			vec.push_back(pi);
			 } 
		 } 
		bool flag=true;
		for(int i=1;i<=4;i++)
			for(int j=1;j<=4;j++){
				if(backup[i][j]=='+'){
					flag=false; vec.clear();
				} 
			}
		if(flag){
			cout<<step<<endl;
			reverse(vec.begin(),vec.end()); 
			for(int i=0;i<vec.size();i++)
				cout<<vec[i].first<<' '<<vec[i].second<<endl;
			return 0;
		}
	}
}

废话版代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
#include<vector>
using namespace std;
/**
最初想到的思路，参照“费解的开关”这道题
枚举，16个位置 有2^16种情况
枚举二进制 0到2^16-1
对于每种情况，对原状态数组进行操作 
*/
const int N=5;
char ch[N][N],backup[N][N]; 
typedef pair<int,int> PII; //pair的用法；又是一个被我遗忘的东西，笑嘻
vector<PII> vec; 

void turn(int i,int j){
	for(int k=1;k<=4;k++){
		if(backup[i][k]=='+') backup[i][k]='-';
		else backup[i][k]='+';
		
		if(backup[k][j]=='+') backup[k][j]='-';
		else backup[k][j]='+';
	}   //当时写的时候，就差点忘记(i,j)的位置翻转了两次，所以下面要再翻回去
	if(backup[i][j]=='+') backup[i][j]='-';
	else backup[i][j]='+';		
}
int main(){
	for(int i=1;i<=4;i++)
		for(int j=1;j<=4;j++)
			cin>>ch[i][j];
			
//一共有2<<16次操作	，枚举
	for(int opt=0;opt<(2<<16);opt++){
		int step=0;
		//memcpy复制数组，不用写双重循环 
		memcpy(backup,ch,sizeof ch);
//		for(int kk=1;kk<=4;kk++)
//			for(int jj=1;jj<=4;jj++)
//				backup[kk][jj]=ch[kk][jj];
//	 	
	 	//对于每个opt，移位16位 
	 	for(int i=0;i<16;i++){
	 		if(opt>>i&1){ //取最低位 ,如果==1的话就翻转；
	 			//例如：0000 0000 0000 0001；最先是1，
				 //第0个对应(4,4) 第1个对应(4,3)
				int row=(16-i-1)/4+1;
				int col= 4-i%4;
				turn(row,col);
	 			step++;
	 			PII pi; pi.first=row;pi.second=col;
	 			vec.push_back(pi);
                //试了一下样例
//	 			if(opt==45067){
//	 				cout<<"step== "<<step<<endl;
//			 		for(int i=1;i<=4;i++){
//						for(int j=1;j<=4;j++)
//							cout<<backup[i][j];
//						cout<<endl; 
//					}
//				 }
			 } 
		 } 

		bool flag=true;
		for(int i=1;i<=4;i++)
			for(int j=1;j<=4;j++){
				if(backup[i][j]=='+'){
					flag=false; vec.clear(); //清空vector;
				} 
			}
			
		if(flag){
			cout<<step<<endl;
			reverse(vec.begin(),vec.end());   //vector的用法忘了，用重新复习下下
			for(int i=0;i<vec.size();i++)
				cout<<vec[i].first<<' '<<vec[i].second<<endl;
			return 0;
		}
	}
}