A.Lake Counting(POJ 2386)

题意：

由于最近的降雨，农夫约翰田地的各个地方都有水汇聚，用N x M（1 <= N <= 100; 1 <= M <= 100）的矩形表示。每个方格包含水（'W'）或干燥土地（'。'）。农夫约翰想弄清楚他的田地里形成了多少个池塘。池塘是一组相连的正方形，里面有水，其中一个正方形被认为与八个池塘相邻
给定农夫约翰的田野图，确定他有多少个池塘。

思路：

染色法，移动可用（-1，0）类似数组，也可以用for循环，注意循环时递归可能会比在main函数里面for循环时间少

1 #include
2 #include
3 #include
4 using namespace std;
5 //染色法，移动可用数组（-1，0）类似，
6 //也可用for循环，递归考虑仔细，他的变换方式
7 int m,n;
8 int k,p,t=1,s=0;
9 char a[101][101];
10 void zhuanhua(int c,int d);
11 void endd();
12 int main(){
13
14 scanf("%d %d",&n,&m);
15 getchar();
16
17 for(k=0;k<n;k++){
18 for(p=0;p<m;p++){
19 scanf("%c",&a[k][p]);
20 }
21 getchar();
22
23 }
24 endd();
25 }
26 void endd(){
27 int k,p,t=0;
28 for(k=0;k<n;k++){
29 for(p=0;p<m;p++){
30 if(a[k][p]=='W'){
31 zhuanhua(k,p);
32 t++;
33 }
34 }
35 }
36 printf("%d",t);
37 }
38 void zhuanhua(int c,int d){
39 if(a[c][d]=='W'){
40 a[c][d]=t;
41 }
42 for(int i=-1;i<2;i++){
43 for(int j=-1;j<2;j++){
44 if(a[c+i][d+j]=='W'){
45 zhuanhua(c+i,d+j);
46 }
47 }
48 }
49 }

B.Red and Black（POJ 1979）

题意：

有一个长方形的房间，覆盖着正方形的瓷砖。每个磁贴都被着色为红色或黑色。一个人站在黑色的瓷砖上。他可以从一个图块移动到四个相邻图块之一。但是他不能在红色瓷砖上移动，只能在黑色瓷砖上移动。
编写一个程序，通过重复上述动作来计算他可以到达的黑色瓷砖的数量。

思路：

大致同A，继续选择用染色的方法

1 #include
2 #include
3 #include
4 #include
5 #include
6 //步骤大致同1
7 using namespace std;
8 int m,n,k,t,f,s,con=0;
9 char c[100][100];
10 int r[5][2]={{-1,0},{1,0},{0,-1},{0,1}};
11 void change(int f,int s);
12 bool panduan(int a,int b);
13 int main(){
14 while(~scanf("%d %d",&m,&n)){
15 if(m==0&&n==0){
16 break;
17 }
18 con=0;
19 getchar();
20 for(k=0;k=n||s+r[a][1]<=-1||s+r[a][1]>=m)continue;
48 if(c[f+r[a][0]][s+r[a][1]]=='.'){
49 change(f+r[a][0],s+r[a][1]);
50
51 }
52 }
53 }

C.Property Distribution（Aizu 0118）

题意：进行相同部分分块

思路：步骤大致同A

1 #include
2 #include
3 #include
4 #include
5 using namespace std;//定义变量时，尽量随用随写，
6 //不然全局变量和局部变量的变化让你找不到bug
7 int h,w;
8 char a[100][100];
9 int r[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
10 void change(int c,int d,char e);
11 int main(){
12
13 while(~scanf("%d %d",&h,&w)){
14 int t=0,m,n;
15 if(h==0&&w==0){
16 break;
17 }
18 getchar();
19 for(m=0;m=h||d+r[s][1]<=-1||d+r[s][1]>=w)continue;
43 if(a[c+r[s][0]][d+r[s][1]]==e){
44 change(c+r[s][0],d+r[s][1],e);
45
46 }
47 }
48 }

D.Ball（Aizu 0033）

题意：

有一个容器分为两个部分。通过容器中的开口A放下编号为1到10的10个球，并将这些球放入左气缸B或右气缸C中。由于板D可以绕支点E左右旋转，因此移动板D可以决定是将其插入圆柱B还是插入C圆柱。给出从开孔A掉落的球的顺序。依次将它们放入试管B或试管C。此时，创建一个程序，如果大球可以同时布置在气缸B和C的小球上，则输出YES，否则将输出NO。但是，球的顺序不能在容器中改变。另外，假定它们可以连续放置在同一管中，并且管B和C都可以容纳所有10个球。

思路：

第一个数肯定是占左边或者右边的第一个，假设占了左边的第一位，左边第二个只能放比第一个数大且是后面比它大的数里面最小的，第三个数对于第二个数也是这样，以此类推…

1 #include
2 #include
3 #include
4 #include
5 #include
6 using namespace std;
7 int a[10],b[10],c[10];
8 void change(int i,int l){
9 int mi,t,s=0,xu=0,sh;
10 mi=110000000;
11 for(t=l+1;t<10;t++){ 12 if(a[t]>i&&a[t]<mi){
13 mi=a[t];
14 xu=t;
15 s=1;
16 }
17 }
18 a[0]=0;
19 a[xu]=0;
20 if(s==1){
21 change(mi,xu);
22 }
23
24 }
25
26 int main(){
27 int n,t,m,k,con=0;
28 scanf("%d",&t);
29 while(t--){
30 con=0;
31 for(m=0;m<10;m++){
32 scanf("%d",&a[m]);
33 b[m]=0;
34 }
35 k=0;
36 change(a[0],0);
37
38 for(m=0;m<10;m++){
39 if(a[m]==0) {continue;}
40 else{
41 b[k]=a[m];
42 c[k]=a[m];
43 k++;
44 }
45 }
46 sort(b,b+k);
47
48 for(m=0;m<k;m++){
49 if(c[m]!=b[m]){
50 con=1;
51
52 }
53 }
54
55 if(con==1){
56 printf("NO\n");
57 }else{
58 printf("YES\n");
59 }
60
61 }
62 }

E.Curling 2.0（POJ 3009）

题意：

在今年的奥运会之后，在MM-21星球上，冰壶正变得越来越流行。但是规则与我们的规则有些不同。该游戏在一块打有方格的冰游戏板上进行。他们只使用一块石头。游戏的目的是以最少的移动次数从一开始就将石头引向目标。

图1显示了游戏板的示例。一些正方形可能被块占据。有两个特殊的方块，即开始和目标，它们没有被方块占据。（这两个正方形是不同的。）一旦石头开始移动，它将继续进行直到碰到一块为止。为了使石头达到目标，您可能必须通过将石头撞在一块上来停止它，然后再次扔。

石头的运动遵循以下规则：

• 刚开始时，石头在起始方块处静止不动。

• 石头的运动仅限于x和y方向。禁止对角移动。

• 当石头静止不动时，可以通过扔石头使其移动。您可以将其朝任何方向扔，除非立即将其阻塞（图2（a））。

• 扔石头后，石头会一直朝着同一方向移动，直到发生以下情况之一：

  • 石头撞到一块（图2（b），（c））。

    • 石头停在撞到的方块旁边的广场上。
    • 块消失。

  • 石头离开了董事会。

    • 游戏以失败告终。

  • 石头到达目标广场。

    • 石头停在那里，游戏成功结束。

在游戏中，扔石头不能超过10次。如果石头在10步中未达到目标，则游戏将失败。

1 #include
2 using namespace std;
3 #define MAX_W 20
4 #define MAX_H 20
5
6 // 待输入的宽度和高度以及已走的步数
7 int W, H;
8 int step = 0;
9 int minStep;
10 int sRow, sCol;
11
12 // 待写入的二维数组
13 int room[MAX_W][MAX_H];
14 // 顺时针的可走方向
15 const int direc[4][2] = {
16 { 0, -1 },
17 { 1,0 },
18 { 0, 1 },
19 { -1 ,0 },
20 };
21
22 void dfs(const int& row, const int& col, int step) {
23 if (step >= 10 || step > minStep) {
24 return;
25 }
26 for (int d = 0; d < 4; ++d) { 27 int cRow = row; 28 int cCol = col; 29 while (cRow >= 0 && cRow < H && cCol >= 0 && cCol < W) { 30 switch (room[cRow][cCol]) { 31 case 0: { 32 cRow += direc[d][1]; 33 cCol += direc[d][0]; 34 break; 35 } 36 case 3: { 37 if (step + 1 < minStep) { 38 minStep = step + 1; 39 } 40 cRow = -1; 41 break; 42 } 43 case 1: { 44 if (!(cRow - direc[d][1] == row && cCol - direc[d][0] == col)) { 45 room[cRow][cCol] = 0; 46 dfs(cRow - direc[d][1], cCol - direc[d][0], step + 1); 47 room[cRow][cCol] = 1; 48 } 49 cRow = -1; 50 break; 51 } 52 default: { 53 break; 54 } 55 } 56 } 57 } 58 } 59 60 int main() 61 { 62 while (cin >> W >> H, W > 0) {
63 // 输入
64 for (int row = 0; row < H; ++row) { 65 for (int col = 0; col < W; ++col) { 66 cin >> room[row][col];
67 }
68 }
69 // 为2的点为起始点
70 for (int row = 0; row < H; ++row) { 71 for (int col = 0; col < W; ++col) { 72 if (room[row][col] == 2) { 73 sRow = row; 74 sCol = col; 75 break; 76 } 77 } 78 } 79 room[sRow][sCol] = 0; 80 minStep = 11; 81 dfs(sRow, sCol, 0); 82 if (minStep > 10) {
83 minStep = -1;
84 }
85 // 输出结果
86 cout << minStep << endl;
87 }
88 }

F.Cheese（Aizu 0558）

题意：

今年JOI镇的奶酪工厂再次开始生产奶酪，一只老鼠从窝里出来。JOI镇分为北，南，东和西，每个地都是巢，奶酪工厂，障碍物或空地。从巢开始，鼠标将访问所有奶酪工厂，并且一次只吃一种奶酪。

这个镇上有N个奶酪工厂，每个工厂只能生产一种奶酪。奶酪的硬度因工厂而异，并且只有一家奶酪工厂生产硬度为1到N的奶酪。

鼠标的初始物理强度为1，每次吃奶酪时，其物理强度都会增加1。但是，老鼠不能吃比身体更坚硬的奶酪。

鼠标可以在1分钟内移动到北，南，东和西的相邻隔间，但不能进入障碍物的隔间。您也可以不吃奶酪就通过奶酪工厂。编写一个程序来查找完成所有奶酪吃完所需的最短时间。但是，可以忽略鼠标吃奶酪的时间。

思路：

简单的bfs，只是比DFS多了通过正确的选择，进行了入栈出栈，判断停止的条件在for循环的外面

1 #include
2 #include
3 #include
4 #include
5 #include
6 using namespace std;
7 typedef pair P;
8 const int inf=0;
9 int b[10000];
10 char a[1000][1000],ts[1000][1000];
11 int d[1000][1000];
12 int sx,sy;
13 int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
14 int h,w,n;
15 int coun(int sx,int sy,int gx,int gy);
16 int main(){
17
18 int sum=0;
19 scanf("%d %d %d",&h,&w,&n);
20 getchar();
21 int k=1,sx=0,sy=0,gx=0,gy=0;
22
23 for(int i = 0; i < h ;i++){ 24 for(int j = 0; j < w ;j++){ 25 26 scanf("%c",&a[i][j]); 27 ts[i][j]=a[i][j]; 28 if(a[i][j]=='S'){ 29 30 sx=i; 31 sy=j; 32 } 33 34 } 35 getchar(); 36 } 37 while(k<=n){ 38 39 for(int i = 0; i < h ;i++){ 40 for(int j = 0; j < w ;j++){ 41 if(ts[i][j]-'0'==k){ 42 gx=i; 43 gy=j; 44 a[i][j]='.'; 45 46 } 47 } 48 } 49 sum+=coun(sx,sy,gx,gy); 50 sx=gx;sy=gy; 51 k++; 52 } 53 printf("%d\n",sum-n); 54 55 56 } 57 int coun(int sx,int sy,int gx,int gy){ 58 queue

que;
59 for(int i=0;i<h;i++){
60 for(int j=0;j<w;j++){
61 d[i][j]=inf;
62 }
63 }
64 que.push(P(sx,sy));
65 d[sx][sy]=1;
66 while(que.size()){
67 P p = que.front();que.pop();
68 if(p.first==gx&&p.second==gy)break;
69 for(int i=0;i<4;i++){
70 int nx=p.first + dx[i],ny = p.second + dy[i];
71 if(0<=nx&&nx<h&&0<=ny&&ny<w&&a[nx][ny]!='X'&&d[nx][ny]==inf){
72 d[nx][ny]=1;
73 que.push(P(nx,ny));
74
75 d[nx][ny]=d[p.first][p.second]+1;
76 }
77 }
78 }
79
80 return d[gx][gy];
81 }

G.Meteor Shower（POJ 3669）

题意：

贝西听说流星雨即将来临。报道说，这些流星将坠入地球并摧毁它们所击中的任何东西。为了安全起见，她发誓要找到一个安全的地方（一个从未被流星破坏的地方）。她目前正在坐标平面上的原点放牧，并希望移至新的更安全的位置，同时避免沿途被流星摧毁。

报告说，中号流星（1≤ 中号 ≤50000）将撞击，与流星我将撞击点（X 我，ÿ 我）（0≤ X 我 ≤300; 0≤ ÿ 我 ≤300）在时间Ť 我（0 ≤ Ť 我   ≤1,000）。每个流星都会破坏其撞击的点以及四个直线相邻的晶格点。

贝西在时间0离开原点，并且可以以每秒一个距离单位的速率在第一象限中平行于轴移动，到达尚未被流星破坏的任何（通常为4个）相邻直线点。不能在大于或等于销毁时间的任何时间将其定位在某个点上。

确定Bessie到达安全地点所需的最短时间。

思路：

给流星雨附近的也进行标记，再进行bfs判断

1 #include
2 #include
3 #include
4 #include
5 using namespace std;
6 int inf=1000000;
7 int dp[400][400]={},sum[400][400]={},fx[1000000]={},fy[1000000]={};
8 int ch[4000][4000];
9 int x,y,z,i,j;
10 int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
11
12 int main(){
13 int sx=0,sy=0,m;
14 scanf("%d",&m);
15 for(int i=0;i<400;i++){ 16 for(int j=0;j<400;j++){ 17 ch[i][j]=inf; 18 } 19 } 20 for(int i=0;i=0&&ny>=0){
26 ch[nx][ny]=min(ch[nx][ny],z);
27 }
28 }
29 }//进行数表坐标最小标记
30
31 int tail=1;
32 sum[0][0]=0;//sum时间
33 fx[1]=0;//分别表示x轴和y轴移动
34 fy[1]=0;
35 for(i=1;i<=tail;i++){ 36 if(ch[fx[i]][fy[i]]>999999){//如果到了安全的地方
37 cout<=0&&yy>=0&&dp[xx][yy]==0&&sum[fx[i]][fy[i]]+1<ch[xx][yy]){
44 dp[xx][yy]=1;
45 sum[xx][yy]=sum[fx[i]][fy[i]]+1;
46 fx[++tail]=xx;
47 fy[tail]=yy;
48 }
49 }
50 }
51 cout<<-1;
52 return 0;
53 }

H.Seven Puzzle（Aizu 0121）

题意：由所给值通过给0及其附近值进行变换从而得到01234567

思路：类似于打表，因为结果已知

1 #include
2 #include

I.Smallest Difference（POJ 2718）

题意：

给定许多不同的十进制数字，您可以通过选择这些数字的非空子集并按一定顺序写入来形成一个整数。其余数字可以按某种顺序写下来以形成第二个整数。除非结果整数为0，否则整数不能以数字0开头
。例如，如果给定数字0、1、2、4、6和7，则可以写成整数对10和2467。当然，有很多方法可以形成这样的整数对：210和764、204和176等。最后一对整数之间的差之和的绝对值为28，结果表明，上述规则可以取得较小的差异。

思路：

暴力全排列，进行数字差值比较

#include
#include
#include
#include
#include
using namespace std;
int a[10],num1,num2;
char str[30];
int main(){
int n,k,con,s;
scanf("%d",&n);
getchar();
while(n--){
k=0;
num1=0;num2=0;
gets(str);
int len=strlen(str);
for(int j=0;j='0'&&str[j]<='9'){
a[k++]=str[j]-'0';
}
}
if(k==2){
printf("%d\n",a[1]-a[0]);
continue;
}else{
int i=0,t=k/2,m=k,s=k/2;
while(a[0]==0)
next_permutation(a,a+k);//进行全排列
int ans=999999999;
do
{//暴力全排列 进行数字比较差值
int mid=(k+1)/2;
if(a[mid])//第二个数不能以零开头
{
int num1=0,num2=0;
for(i=0;i<mid;++i)
num1=num1*10+a[i];
for(i=mid;i<k;++i)
num2=num2*10+a[i];
ans=min(ans,abs(num1-num2));
}
}while(next_permutation(a,a+k));
printf("%d\n",ans);
}
}
}

J.Backward Digit Sums（POJ 3187）

题意：类似于杨辉三角

#include
#include
#include
#include
using namespace std;
int a[20],v[20];
int num(int *a,int n){
int i,j,t=n;
for(i=1;i<n;i++){
for(j=0;j<t;j++){
a[j]=a[j]+a[j+1];
}
t--;
}
return a[0];
}int main(){
memset(v,0,sizeof(v));
int i,n,sum;
scanf("%d %d",&n,&sum);
for(i=0;i<n;i++){
v[i]=i+1;
}
while(1){
for(int i=0;i<n;i++){
a[i]=v[i];
}//用另一股数组 进行计算 自身数组记录状态
if(num(a,n)==sum) break;
next_permutation(v,v+n);
}
printf("%d",v[0]);
for(int i=1;i<n;i++){
printf(" %d",v[i]);
}
printf("\n");
return 0;
}

K.Hopscotch（POJ 3050）

题意：查找数表中，可以组成多少个不同的数

思路：bfs进行查找，set进行排重即可

#include
#include
#include
#include
#include
#include
using namespace std;
long long a[5][5];
set s;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0},st[6]={};
int dfs(int x,int y,int z);
int main(){
int m,n;
for(m=0;m<5;m++){ for(n=0;n<5;n++){ scanf("%d",&a[m][n]); } } for(m=0;m<5;m++){//想要换开头就得这么循环 for(n=0;n<5;n++){ st[0]=a[m][n]; dfs(m,n,1);//巧妙计数 } } printf("%d\n",s.size()); } int dfs(int x,int y,int z){ int sum,k; if(z==6){ sum=st[0]*100000+st[1]*10000+st[2]*1000+st[3]*100+st[4]*10+st[5]; s.insert(sum); return 0; } for(k=0;k<4;k++){ int nx=x+dx[k],ny=y+dy[k]; if(nx>=0&&ny>=0&&nx<5&&ny<5){//找到第二个数了 告诉他自己是第二个数
st[z]=a[nx][ny];//先进数组再进行统一计算
dfs(nx,ny,z+1);
}

}  

}

L.Osenbei（Aizu 0525）

题意：

进行翻转0变1，1变0，输出1最多的数量

思路：

递归变换查找，固定一个变量进行参考，让列数变换去查找
    递归从不变到变一列变两列到核实最后一列变换以后，进行统计，边变换，边记录统计

#include
#include
#include
#include
using namespace std;
int a[100][10000];
int cou(int line);
int ans=0;
int m,n;
int main(){

while(~scanf("%d %d",&m,&n)){  
    if(m==0&&n==0) break;  
    for(int i=0;i<m;i++){  
        for(int j=0;j<n;j++){  
            scanf("%d",&a\[i\]\[j\]);  
        }  
    }  
    cou(0);  
    printf("%d\\n",ans);

}
}
int cou(int line){//递归变换查找，固定一个变量进行参考，让列数变换去查找
//递归从不变到变一列变两列到核实最后一列变换以后，进行统计，边变换，边记录统计

if(line==m){  
    int sum=0;  
    for(int i=0;i<n;i++){  
        int l=0;  
        for(int j=0;j<m;j++){  
            if(a\[j\]\[i\]==0){  
                l++;  
            }  
        }  
        sum+=max(l,m-l);  
    }  
    return ans=max(ans,sum);

}  
cou(line + 1);  
for(int i = 0; i < n; i++){  
    if(a\[line\]\[i\]==1){  
        a\[line\]\[i\]=0;  
    }else{  
        a\[line\]\[i\]=1;  
    }  
}  
cou(line + 1);  

}

DFS：

1.if判断一般会在循环外（即如果前n项都计算过了…），或者在循环的下面，即循环已经走完，所有的开头已经试验；

2.染色后，改变初始状态，便于分辨是否已经染过色；

3.判断是否重新进递归时，记得看是否越界，判断条件记得写好

BFS：

1.将所有位置初始化（距离d[i][j]数组）=> 利用队列queue，题目已经起点入列 => 不断循环直到队列长度为0 => 从队最前端取出元素，再pop => 如果状态已经是终点，则结束 => 不同方向进行循环，移动之后进行位置记录 => 判断是否访问过以及是否可移动  => 可移动则加入队列，到该位置d[i][j]+1

END：

1.学习记住next_permutation，进行全排列

2.整清楚全局变量和局部变量，否则影响答案还找不到错误

3.打表的用处，结果已知，多个样例

（简：全排列、变量位置、if位置、打表）