POJ 1753-Flip Game
Flip Game
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 31655 Accepted: 13776
Description
Flip game is played on a rectangular 4×4 field with two-sided pieces placed on each of its 16 squares. One side of each piece is white and the other one is black and each piece is lying either it’s black or white side up. Each round you flip 3 to 5 pieces, thus changing the color of their upper side from black to white and vice versa. The pieces to be flipped are chosen every round according to the following rules:
Choose any one of the 16 pieces.
Flip the chosen piece and also all adjacent pieces to the left, to the right, to the top, and to the bottom of the chosen piece (if there are any).
Consider the following position as an example:
bwbw
wwww
bbwb
bwwb
Here “b” denotes pieces lying their black side up and “w” denotes pieces lying their white side up. If we choose to flip the 1st piece from the 3rd row (this choice is shown at the picture), then the field will become:
bwbw
bwww
wwwb
wwwb
The goal of the game is to flip either all pieces white side up or all pieces black side up. You are to write a program that will search for the minimum number of rounds needed to achieve this goal.
Input
The input consists of 4 lines with 4 characters “w” or “b” each that denote game field position.
Output
Write to the output file a single integer number – the minimum number of rounds needed to achieve the goal of the game from the given position. If the goal is initially achieved, then write 0. If it’s impossible to achieve the goal, then write the word “Impossible” (without quotes).
Sample Input
bwwb
bbwb
bwwb
bwww
Sample Output
4
Source
Northeastern Europe 2000
题意：翻动格子使得整个棋盘为全黑或者全白，求最少的翻动次数，翻动某一个格子，也会同时翻动其周围的四个格子（如果有的话）。因为某一个格子翻动2次的结果和不翻是一样的；翻动3次的结果和翻动1次的结果是一样的；多个也是一样，所以一个格子最多翻动1次，这样总的翻动次数最多为16次。每个格子有翻和不翻两种情况，所以总共有$$2^{16}$$种情况，可以暴力枚举。 但是一直没有想好用哪种方法，深度搜索还是广度搜索。后来想了想，这是求最优解（最少翻动次数）的题，所以用广度优先搜索的效率应该会高一些，但是在BFS的过程中曾有一个问题困扰了，后面再说。又因为棋盘正好是4*4=16的，可以用int的位运算来表示，b表示1，w表示0，这样棋盘的一个状态就可以用一个int数来表示，翻动格子也可以用位运算来表示，总共的状态数是$$2^{16}$$，取值范围是[0,65535]，当棋盘状态是0或者65535时，表示全白或者全黑，这时找到结果。 了解了这些，就可以写出BFS+位运算的代码了，这题我是参考了网上的题解： [cpp] #include<iostream> #include<queue> using namespace std; const int MAX_STATUS=65536;//2^16=65536种，所以[0,65535] const int ALL_0=0;//全0 const int ALL_1=65535;//全1 int ans; int visited[MAX_STATUS]={0};//访问标记 typedef struct POS//position翻转位置 { int val;//当前翻转状态的值 int step;//到当前状态共翻转了多少次 }; //广搜 void BFS(int init_id) { queue<POS> Q_P; POS s,next_p; //初始位置 s.val=init_id; s.step=0; visited[s.val]=1; Q_P.push(s); while(!Q_P.empty()) { s=Q_P.front(); Q_P.pop(); if(s.val==ALL_0||s.val==ALL_1)//找到结果 { ans=s.step; return; } //尝试翻16个位置 for(int i=0;i<4;i++) { for(int j=0;j<4;j++) { next_p.val=s.val; //测试i，翻转[i,j]上下位置的格子 if(i==0) next_p.val^=1<<(11-4*i-j); else if(i==3) next_p.val^=1<<(19-4*i-j); else { next_p.val^=1<<(11-4*i-j); next_p.val^=1<<(19-4*i-j); } //测试j，翻转[i,j]左右位置的格子 if(j==0) next_p.val^=3<<(14-4*i-j); else if(j==3) next_p.val^=3<<(15-4*i-j); else next_p.val^=7<<(14-4*i-j); if(visited[next_p.val]==0)//如果没有访问 { visited[next_p.val]=1;//访问 next_p.step=s.step+1;//翻转次数加1 Q_P.push(next_p);//并加入队列 } } } } ans=-1;//到这里还没有return,说明impossible } int main() { //freopen("input.txt","r",stdin); char c; int id=0; //输入转换 /*bwbw wwww bbwb bwwb 排列成bwbw wwww bbwb bwwb，然后把b换成1，w换成0*/ for(int i=0;i<4;i++) { for(int j=0;j<4;j++) { cin>>c; id<<=1; if(c==’b’)//b=1;w=0 id+=1; } } BFS(id); if(ans==-1) cout<<"Impossible"; else cout<<ans; return 0; } [/cpp] 本代码提交AC，用时79MS，内存508K。 在每一次BFS的时候，我们都要尝试去翻所有16个格子，如果翻动之后达到了一个新的状态（也就是之前没有访问过），说明这个翻动是有效的，把它加入到队列中。在翻动的时候，怎样进行位运算大家可以把i=0,j=0代入到for循环里手算一遍，程序会根据i和j的不同，和不同的数进行异或运算。 之前我说有一个地方让我困惑，就是我之前：第一次BFS的时候肯定把所有格子都翻了一遍，也就是把(0,0)(0,1)…(3,3)翻动的结果都加入到队列中了，那么在第二次BFS的时候，把(0,0)出队，这个时候再来翻所有16个格子，这样不就相当于把所有格子又翻回到初始状态了吗？其实这种想法是不对的，说到底还是对BFS理解不够透彻。**我们在每次BFS的时候都是在队首元素的基础上翻转的，因为我们在while开头执行了s=Q_P.front();Q_P.pop();这么两句**，那么当我们把(0,0)翻转状态出队在去翻转的时候，是在(0,0)翻转状态的基础是再进行翻转的，而这个时候是只有(0,0)这一个格子翻了，其他15个格子都没有翻；同理当把(0,1)出队的时候，也是只有(0,1)翻了，其他15个都没有翻。所以这样BFS下去是能够搜索到所有状态的。 纵观所有BFS题目，套路都是一样的。]]>
快速得到$$sin\theta=1/\sqrt{1+(CRw)^2}$$，代入⑨式得到最终结果：$$V_R=CRwV_S/\sqrt{1+(CRw)^2}$$
得到了公式，快速写出代码：
[cpp]
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
int main()
{
//freopen("input.txt","r",stdin);
double vs,r,c,w,vr;
int n;
cin>>vs>>r>>c>>n;
while(n–)
{
cin>>w;
vr=c*r*w*vs/sqrt(1+c*r*w*c*r*w);
printf("%.3lf\n",vr);
}
return 0;
}
[/cpp]
本代码提交AC，用时0MS，内存208K。
]]>
Input
The input data will start with the number of the test cases. For each test case, 9 lines follow, corresponding to the rows of the table. On each line a string of exactly 9 decimal digits is given, corresponding to the cells in this line. If a cell is empty it is represented by 0.
Output
For each test case your program should print the solution in the same format as the input data. The empty cells have to be filled according to the rules. If solutions is not unique, then the program may print any one of them.
Sample Input
1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107
Sample Output
143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127
Source
Southeastern Europe 2005
假设分别从A点和B点开始的单源最短距离如上两张图所示，那么Stockbroker从A点开始传播谣言总共需要多长时间呢？因为传播是可以同时进行的，所以传播结束时间就是A点到其他点中的最长距离，也就是上图中的AC。同理，如果从B点开始，则|BD|是传播时间。
综上所述，本题的求解过程可以归纳为以下几步：
1. 测试图中的每一个点$$i$$，求从该点出发，到其他所有点的单源最短距离集合$$S_i$$
2. 求出该单源最短距离$$S_i$$内部的最大值$$M_i$$
3. 对于图中的所有点，求其$$M_i$$
4. 最后求所有$$M_i$$中的最小值$$MIN$$，即为最终结果
所以根据上面的步骤，我们可以用n次Dijkstra算法求每个点的单源最短距离内部的最大值$$M_i$$，然后求$$MIN$$。其实也可以不用这么麻烦，因为我们还有另外一个更简单的算法Floyd算法。使用Floyd算法求得所有点对的最短距离，自然就知道某个点的单源最短距离了。
在写代码的时候还有一些小问题需要注意，对于数据输入，请仔细多读几遍Input说明，如果还是有困难，请看