kuangbin 专题一 简单搜索

1.POJ1321棋盘问题[DFS]

问题链接.

代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=10;
int n,k,ans,num;
char g[N][N];
bool col[N];
void dfs(int x)
{if(num==k) {ans++;return;}if(x==n){return;}for(int i=0;i<n;i++){if(g[x][i]=='#'&&col[i]==0){num++;col[i]=1;dfs(x+1);col[i]=0;num--;}}dfs(x+1);
}
int main()
{while(cin>>n>>k){if(n==-1&&k==-1) return 0;ans=num=0;memset(col,0,sizeof(col));for(int i=0;i<n;i++)cin>>g[i];dfs(0);cout<<ans<<"\n";}return 0;
}

自己的想法

八皇后变形问题，区别在于没有斜边的要求，棋盘区域是不规则的。

2.POJ2251Dungeon Master[三维空间BFS]

问题链接.

代码

#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=35;
int dx[]={1,-1,0,0,0,0},dy[]={0,0,1,-1,0,0},dz[]={0,0,0,0,1,-1};
int x,y,z,Sx,Sy,Sz,Ex,Ey,Ez;
char g[N][N][N];
int d[N][N][N];
bool vis[N][N][N];
struct Node{int x,y,z;
};
int bfs()
{queue<Node> q;q.push({Sx,Sy,Sz});while(q.size()){Node t=q.front();q.pop();if(t.x==Ex&&t.y==Ey&&t.z==Ez){return d[t.x][t.y][t.z];}for(int i=0;i<6;i++){int xx=t.x+dx[i];int yy=t.y+dy[i];int zz=t.z+dz[i];if(g[xx][yy][zz]!='#'&&xx>=0&&xx<x&&yy>=0&&yy<y&&zz>=0&&zz<z&&!vis[xx][yy][zz]&&!d[xx][yy][zz]){vis[xx][yy][zz]=1;d[xx][yy][zz]=d[t.x][t.y][t.z]+1;q.push({xx,yy,zz});}}	}return -1;
}
int main()
{while(cin>>x>>y>>z){if(x==0) return 0;memset(d,0,sizeof(d));memset(vis,0,sizeof(vis));//getchar();for(int i=0;i<x;i++){for(int j=0;j<y;j++){for(int k=0;k<z;k++){//scanf("%c",g[i][j][k]);cin>>g[i][j][k];if(g[i][j][k]=='E')Ex=i,Ey=j,Ez=k;else if(g[i][j][k]=='S'){Sx=i,Sy=j,Sz=k;vis[i][j][k]=1;}}}} int ans=bfs();if(ans!=-1) printf("Escaped in %d minute(s).\n",ans);else printf("Trapped!\n");}return 0;
}

自己的想法

第一次遇见三维BFS最短路，不过比较简单。

3.POJ3278 Catch That Cow[BFS]

问题链接.

代码

#include<iostream>
#include<stdio.h>
#include<queue>
#include<cstring>
using namespace std;
const int N=1e5+10;
int dx[]={-1,1,2};
int n,k,ans=0;
bool st[N];
int d[N];
int bfs(int x)
{queue<int> q;q.push(x);st[x]=1;d[x]=0;while(q.size()){int t=q.front();if(t==k){break;}q.pop();for(int i=0;i<3;i++){int a;if(i!=2)a=t+dx[i];else a=2*t;if(st[a]||a<0||a>100000) continue;st[a]=1;q.push(a);
//			cout<<a<<" ";d[a]=d[t]+1;}}return d[k];
}
int main()
{scanf("%d%d",&n,&k); cout<<bfs(n);return 0;
}

自己的想法

直接BFS模拟即可。

4.POJ3279 Fliptile[状态压缩+DFS]

问题链接.

代码

#include<algorithm>
#include<iostream>
#include<string>
using namespace std;const int N=20;
bool g[N][N],tmp[N][N];
int cnt[N][N];
string ans;
int n,m;
void change(int x,int y)//翻转模块
{tmp[x][y]=!tmp[x][y];if(x-1>=0)tmp[x-1][y]=!tmp[x-1][y];if(x+1<n)tmp[x+1][y]=!tmp[x+1][y];if(y-1>=0)tmp[x][y-1]=!tmp[x][y-1];if(y+1<m)tmp[x][y+1]=!tmp[x][y+1];
}
void init()//初始化
{for(int i=0;i<n;i++)for(int j=0;j<m;j++)tmp[i][j]=g[i][j];
}bool check()//检查是否可以
{for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(tmp[i][j])return 0;return 1;
}int main()
{while(~scanf("%d%d",&n,&m)){ans="";for(int i=0;i<n;i++)for(int j=0;j<m;j++){scanf("%d",&g[i][j]);tmp[i][j]=g[i][j];}int min_count=0x3f3f3f3f;for(int i=0;i<(1<<m);i++)//枚举第一行方案{init();int count=0;string str="";for(int j=0;j<m;j++)if(i&(1<<j)){change(0,j);str+='1';count++;}else str+='0';for(int j=1;j<n;j++)for(int k=0;k<m;k++)if(tmp[j-1][k]){change(j,k);str+='1';count++;}else str+='0';if(check())//更新答案{if(count<min_count){min_count=count;ans=str;}else if(count==min_count)//字典序比较更新{if(str<ans){ans=str;}}}}if(min_count!=0x3f3f3f3f)//输出答案{for(int i=0;i<n;i++){for(int j=0;j<m;j++){printf("%c ",ans[i*m+j]);}puts("");}}else puts("IMPOSSIBLE");}return 0;
}

自己的想法

这道题一开始我没啥思路，可以参考下大佬的思路。
大佬的思路：
选与不选（二进制枚举），类似题目是蓝书上费解的开关
有以下性质：
1：每个点最多点一次
2：如果第一行已经固定，那么满足题意的点击方案最多只有一种。因为当第i行某位为1时，若前i行已经被固定，那么只能点击第i+1行该位置上的数字才能使第i行变为0,归纳后可以得到此结论（所以我们只要枚举第一行方案即可）
3：点击的先后顺序不影响结果(做搜索的时候要确定操作选择顺序是否会影响答案）

这题要求最小操作数并输出字典序最小的，那么我们可以把输出的二维数组压缩为string字符串，如果当前方案数量和已有最小数量相等比较ans和当前方案的字符串并更新

参考链接

5.POJ1426 Find The Multiple[BFS]

问题链接.

代码

#include<iostream>
#include<queue>
#include<stdio.h>
using namespace std;
typedef long long ll;
ll n;
ll bfs()
{queue<ll>q;q.push(1);while(!q.empty()){ll t=q.front();q.pop();if(t%n==0&&t>=n)return t;q.push(t*10);q.push(t*10+1);}
}
int main()
{while(~scanf("%lld",&n)&&n){printf("%lld\n",bfs());}return 0;
}

自己的想法

这道题肯定不能直接暴力枚举倍数判断是否全为1或0，这样会超时的，我们可以另辟蹊径，枚举1，10，11，110…，判断是否为非0倍数，这样做就非常巧妙的解决了这个问题，而枚举这些可以用上BFS。另外要注意用long long！

6.POJ3126 Prime Path[BFS]

问题链接.

代码

#include<iostream>
#include<queue>
#include<stdio.h>
#include<string.h> 
using namespace std;
typedef long long ll;
const int N=1e5+5;
int vis[N],p[N],f[N],t,n,m,d[N];
void init()
{   int tot=0;memset(vis,0,sizeof(vis));memset(p,0,sizeof(p));vis[0]=vis[1]=1;for(int i=2;i<=N;i++){if(vis[i]==0){p[tot++]=i;f[i]=i;}for(int i1=0;i1<tot&&N>=p[i1]*i;i1++){vis[i*p[i1]]=1;f[i*p[i1]]=p[i1];if(i%p[i1]==0)		break;	}}}
int change(int x,int y,int z)
{int a=z/1000;int b=z/100%10;int c=z/10%10;int d=z%10;int ans;if(x==0){ans=y*1000+b*100+c*10+d;if(ans>=1000)return ans;else return -1;}else if(x==1){ans=a*1000+y*100+c*10+d;if(ans>=1000)return ans;else return -1;}else if(x==2){ans=a*1000+b*100+y*10+d;if(ans>=1000)return ans;else return -1;}else if(x==3){ans=a*1000+b*100+c*10+y;if(ans>=1000)return ans;else return -1;}
}
int bfs()
{queue<int> q;q.push(n);
//	cout<<n;memset(d,-1,sizeof d);d[n]=0;while(q.size()){int tt=q.front();
//		cout<<tt<<" ";q.pop();if(vis[tt]) continue;if(tt==m) return d[tt];for(int i=0;i<4;i++){for(int j=0;j<10;j++){int cnt=change(i,j,tt);
//				cout<<cnt<<" ";if(d[cnt]==-1&&vis[cnt]==0&&cnt!=-1){d[cnt]=d[tt]+1;q.push(cnt);}}		}}return -1;
}
int main()
{init();scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);		if(bfs()!=-1)printf("%d\n",bfs());else printf("Impossible\n");}return 0;
}

自己的想法

这道题就是线性筛+BFS，在BFS中，我是以四位数字，每位数字有10种选择来循环操作，思路还是很清晰的，码量稍微大了点。

7.POJ3087 Shuffle’m Up[简单模拟]

Time Limit: 1000MS Memory Limit: 65536K

Description:

A common pastime for poker players at a poker table is to shuffle stacks of chips. Shuffling chips is performed by starting with two stacks of poker chips, S1 and S2, each stack containing C chips. Each stack may contain chips of several different colors.

The actual shuffle operation is performed by interleaving a chip from S1 with a chip from S2 as shown below for C = 5:

The single resultant stack, S12, contains 2 * C chips. The bottommost chip of S12 is the bottommost chip from S2. On top of that chip, is the bottommost chip from S1. The interleaving process continues taking the 2nd chip from the bottom of S2 and placing that on S12, followed by the 2nd chip from the bottom of S1 and so on until the topmost chip from S1 is placed on top of S12.

After the shuffle operation, S12 is split into 2 new stacks by taking the bottommost C chips from S12 to form a new S1 and the topmost C chips from S12 to form a new S2. The shuffle operation may then be repeated to form a new S12.

For this problem, you will write a program to determine if a particular resultant stack S12 can be formed by shuffling two stacks some number of times.

Input:

The first line of input contains a single integer N, (1 ≤ N ≤ 1000) which is the number of datasets that follow.

Each dataset consists of four lines of input. The first line of a dataset specifies an integer C, (1 ≤ C ≤ 100) which is the number of chips in each initial stack (S1 and S2). The second line of each dataset specifies the colors of each of the C chips in stack S1, starting with the bottommost chip. The third line of each dataset specifies the colors of each of the C chips in stack S2 starting with the bottommost chip. Colors are expressed as a single uppercase letter (Athrough H). There are no blanks or separators between the chip colors. The fourth line of each dataset contains 2 * C uppercase letters (A through H), representing the colors of the desired result of the shuffling of S1 and S2 zero or more times. The bottommost chip’s color is specified first.

Output:

Output for each dataset consists of a single line that displays the dataset number (1 though N), a space, and an integer value which is the minimum number of shuffle operations required to get the desired resultant stack. If the desired result can not be reached using the input for the dataset, display the value negative 1 (?1) for the number of shuffle operations.

Sample Input:

2
4
AHAH
HAHA
HHAAAAHH
3
CDE
CDE
EEDDCC

Sample Output:

1 2
2 -1

代码

#include<iostream>
#include<queue>
#include<stdio.h>
#include<string.h> 
using namespace std;
int n,c,d;
string s1,s2,s12,temp;
int main()
{int t;scanf("%d",&t);for(int i=1;i<=t;i++){cin>>c;cin>>s1>>s2>>s12;int cnt=0,flag=0,num=0;while(num<700){temp="";cnt++;for(int i=0;i<c;i++){temp = temp + s2[i] + s1[i];}if(temp==s12) {flag=1;break;}s1=temp.substr(0,c),s2=temp.substr(c);num++;}if(flag){printf("%d %d\n",i,cnt);}else cout<<i<<" "<<-1<<endl;}return 0;
}

自己的想法

直接模拟即可，不需要搜索。

8.POJ3414 Pots[BFS]

Time Limit: 1000MS Memory Limit: 65536K

Description:

You are given two pots, having the volume of A and B liters respectively. The following operations can be performed:

1.FILL(i) fill the pot i (1 ≤ i ≤ 2) from the tap;
2.DROP(i) empty the pot i to the drain;
3.POUR(i,j) pour from pot i to pot j; after this operation either the pot j is full (and there may be some water left in the pot i), or the pot i is empty (and all its contents have been moved to the pot j).

Write a program to find the shortest possible sequence of these operations that will yield exactly C liters of water in one of the pots.

Input:

On the first and only line are the numbers A, B, and C. These are all integers in the range from 1 to 100 and C≤max(A,B).

Output:

The first line of the output must contain the length of the sequence of operations K. The following K lines must each describe one operation. If there are several sequences of minimal length, output any one of them. If the desired result can’t be achieved, the first and only line of the file must contain the word ‘impossible’.

Sample Input:

3 5 4

Sample Output:

6
FILL(2)
POUR(2,1)
DROP(1)
POUR(2,1)
FILL(2)
POUR(2,1)

代码

#include<iostream>
#include<queue>
#include<stdio.h>
#include<string.h> 
using namespace std;
int a,b,c,d[105][105];
string Path[]={"FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"};
struct node{int a,b;string p;
};
node change(int x,int y,node t)
{if(x==0){if(y==0){return {a,t.b,t.p+'0'};}else return {t.a,b,t.p+'1'};}else if(x==1){if(y==0){return {0,t.b,t.p+'2'};}else return {t.a,0,t.p+'3'};}else{if(y==0){if(t.a+t.b>=b) return {t.a+t.b-b,b,t.p+'4'};else return {0,t.a+t.b,t.p+'4'};}else{if(t.a+t.b>=a) return {a,t.a+t.b-a,t.p+'5'};else return {t.a+t.b,0,t.p+'5'};}}
}
void bfs()
{queue<node> q;q.push({0,0,""});memset(d,-1,sizeof d);d[0][0]=0;while(q.size()){node t=q.front();q.pop();if(t.a==c||t.b==c){cout<<d[t.a][t.b]<<endl;string ans=t.p;for(int i=0;i<d[t.a][t.b];i++) {cout<<Path[ans[i]-'0']<<endl;
//				cout<<ans<<endl;}return;} for(int i=0;i<3;i++){for(int j=0;j<2;j++){node x=change(i,j,t);if(d[x.a][x.b]==-1){d[x.a][x.b]=d[t.a][t.b]+1;q.push({x.a,x.b,x.p});}}		}}cout<<"impossible";return;
}
int main()
{cin>>a>>b>>c;bfs();return 0;
}

自己的想法

这道题比较难，难在怎么输出步骤，我也是参考了大佬思路才写出来的。

9.FZU2150 Fire Game[BFS+暴力]

Description:

Fat brother and Maze are playing a kind of special (hentai) game on an N*M board (N rows, M columns). At the beginning, each grid of this board is consisting of grass or just empty and then they start to fire all the grass. Firstly they choose two grids which are consisting of grass and set fire. As we all know, the fire can spread among the grass. If the grid (x, y) is firing at time t, the grid which is adjacent to this grid will fire at time t+1 which refers to the grid (x+1, y), (x-1, y), (x, y+1), (x, y-1). This process ends when no new grid get fire. If then all the grid which are consisting of grass is get fired, Fat brother and Maze will stand in the middle of the grid and playing a MORE special (hentai) game. (Maybe it’s the OOXX game which decrypted in the last problem, who knows.)

You can assume that the grass in the board would never burn out and the empty grid would never get fire.

Note that the two grids they choose can be the same.

Input:

The first line of the date is an integer T, which is the number of the text cases.

Then T cases follow, each case contains two integers N and M indicate the size of the board. Then goes N line, each line with M character shows the board. “#” Indicates the grass. You can assume that there is at least one grid which is consisting of grass in the board.

1 <= T <=100, 1 <= n <=10, 1 <= m <=10

Output:

For each case, output the case number first, if they can play the MORE special (hentai) game (fire all the grass), output the minimal time they need to wait after they set fire, otherwise just output -1. See the sample input and output for more details.

Sample Input:

4
3 3
.#.
###
.#.
3 3
.#.
#.#
.#.
3 3
...
#.#
...
3 3
###
..#
#.#

Sample Output:

Case 1: 1
Case 2: -1
Case 3: 0
Case 4: 2

代码

#include<bits/stdc++.h>
using namespace std;
const int N=15;
int d[N][N],n,m;
char g[N][N];
#define inf 0x3f3f3f3f
int dx[]={-1,1,0,0},dy[]={0,0,1,-1};
struct node{int x,y;
};
int bfs(int x1,int y1,int x2,int y2)
{queue<node> q;q.push({x1,y1});q.push({x2,y2});memset(d,-1,sizeof d);d[x1][y1]=d[x2][y2]=0;while(q.size()){node t=q.front();q.pop();for(int i=0;i<4;i++){int x=t.x+dx[i];int y=t.y+dy[i];if(d[x][y]==-1&&x>=0&&x<n&&y>=0&&y<m&&g[x][y]=='#'){d[x][y]=d[t.x][t.y]+1;q.push({x,y});			}}}	int res=0;for(int i=0;i<n;i++)for(int j=0;j<m;j++){if(g[i][j]=='#'){if(d[i][j]==-1)return -1;else res=max(res,d[i][j]);}	}return res;
}
int main()
{int t;cin>>t;for(int k=1;k<=t;k++){cin>>n>>m;for(int i=0;i<n;i++)for(int j=0;j<m;j++){cin>>g[i][j];}int ans=inf;for(int i=0;i<n;i++)for(int j=0;j<m;j++)for(int p=0;p<n;p++)for(int r=0;r<m;r++){if(g[i][j]=='#'&&g[p][r]=='#'){int temp=bfs(i,j,p,r);if(temp==-1)continue;							ans=min(ans,temp);}}if(ans==0x3f3f3f3f)ans=-1;printf("Case %d: %d\n",k,ans);}return 0;
}

自己的想法

这道题好暴力，我估计复杂度有10的8次方了。。。就BFS+暴力枚举两个起点。不过两个起点放在一个队列里面我还是第一次遇见，换做我一开始的思路是两次BFS，也算提供了另一种思路吧。
参考链接

10.UVA11624 Fire![BFS]

Description:

乔在迷宫中工作。不幸的是，迷宫的一部分着火了，迷宫的主人没有制定火灾的逃跑计划。请帮助乔逃离迷宫。根据乔在迷宫中的位置以及迷宫的哪个方块着火，你必须确定火焰烧到他之前，乔是否可以离开迷宫，如果能离开他能跑多快。
乔和火每分钟移动一个方格，上、下、左、右，四个方向中的一个。火势向四个方向同时蔓延。乔可以从迷宫的任何一个边界逃离迷宫。无论是乔还是火都不会到达有墙的位置。

Input：

第一行输入包含一个整数，即测试次数
每个测试用例的第一行包含两个
整数R和C，用空格分隔，1≤R，C≤1000
下面R行中，每一行都包含C个字符，以及每个字符是以下之一：
#代表墙
.代表空地，火和乔是可通行的
J 乔在迷宫中最初的位置，火和乔是可通行的
F 代表火
在每组测试中只有一个J

Output:

对于每个测试用例，如果在火蔓延的时候烧到了乔，则乔无法逃出迷宫，输出’IMPOSSIBLE’如果乔能逃出迷宫，则输出乔最快可以在几分钟内安全逃出迷宫，每组输出占一行

Sample Input:

2
4 4
####
#JF#
#..#
#..#
3 3
###
#J.
#.F

Sample Output:

3
IMPOSSIBLE

代码

#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=1005;
char g[N][N];
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
int t,r,c,Jx,Jy,vis[N][N];
struct Node{int x,y;
};
int bfs()
{queue<Node> q;queue<Node> Fq;memset(vis,0,sizeof(vis));for(int i=0;i<r;i++){for(int j=0;j<c;j++){if(g[i][j]=='J'){Jx=i,Jy=j;vis[i][j]=1;	}else if(g[i][j]=='F'){Fq.push({i,j});g[i][j]='#';}}} q.push({Jx,Jy});int step=0;while(q.size()){step++;for(int i=0,j=q.size();i<j;i++){Node t=q.front();q.pop();if (g[t.x][t.y] == '#') continue; for(int k=0;k<4;k++){int a=t.x+dx[k];int b=t.y+dy[k];if(a==r||b==c) return step;if(g[a][b]!='#'&&vis[a][b]!=1){q.push({a,b});vis[a][b]=1;}}}for(int i=0,j=Fq.size();i<j;i++){Node t=Fq.front();Fq.pop();for(int k=0;k<4;k++){int a=t.x+dx[k];int b=t.y+dy[k];if(a>=0&&a<r&&b>=0&&b<c&&g[a][b]!='#'){Fq.push({a,b});g[a][b]='#';}}}}return 0;
}
int main()
{cin>>t;while(t--){cin>>r>>c;	for(int i=0;i<r;i++)cin>>g[i];int ans=bfs();if(ans) cout<<ans<<"\n";else cout<<"IMPOSSIBLE\n";}return 0;
}

自己的想法

有两种写法，一种先把Fire全部蔓延预处理出每个点到火的最短距离（注意有多个火的源点）然后再让Joe BFS一遍，必须距离小于火到这里的距离才可以，另一种是同时走，同一秒内人先走然后火再蔓延。这里是用了后一种写法。后一种写法有几个需要注意的点:
1.注意一开始J只有一个，但F可以有多个！
2.

step++;for(int i=0,j=q.size();i<j;i++){...

step++后面的for循环必须要加！
3.

step++;for(int i=0,j=q.size();i<j;i++){Node t=q.front();q.pop();if (g[t.x][t.y] == '#') continue; ......

if (g[t.x][t.y] == ‘#’) continue; 这个语句必须要加！因为是人先走，火再蔓延。
参考链接

11.POJ3984 迷宫问题[BFS]

Time Limit: 1000MS Memory Limit: 65536K

Description:

定义一个二维数组：

int maze[5][5] = {

0, 1, 0, 0, 0,0, 1, 0, 1, 0,0, 0, 0, 0, 0,0, 1, 1, 1, 0,0, 0, 0, 1, 0,

};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

Input:

一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。

Output:

左上角到右下角的最短路径，格式如样例所示。

Sample Input:

0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

Sample Output:

(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

代码

#include<iostream>
#include<cstring>
#include<string>
#include<queue>
#include<stdio.h>
using namespace std;
int maze[10][10];
int dx[]={0,1,-1,0},dy[]={1,0,0,-1};
int x1=0,y1=0;
int x2=4,y2=4;
struct node{int x,y;string s;
};
void bfs()
{queue<node> q;q.push({x1,y1,"00"});while(q.size()){node t=q.front();q.pop();if(t.x==4&&t.y==4){string s=t.s;for(int i=0;i<s.length();i+=2){printf("(%c, %c)\n",s[i],s[i+1]);}return;}for(int i=0;i<4;i++){int x=t.x+dx[i];int y=t.y+dy[i];if(x>=0&&x<=4&&y>=0&&y<=4&&maze[x][y]==0){char c=('0'+x);string s=t.s+c;c=('0'+y);s+=c;q.push({x,y,s});maze[x][y]=1;}}}
}
int main()
{for(int i=0;i<5;i++)for(int j=0;j<5;j++)cin>>maze[i][j];bfs();return 0;
}

自己的想法

这道题时典型的BFS样题，这里的难点在于如何记录路径，我们可以在struct里定义一个字符串变量来记录路径将路径坐标记录在字符串里输出就行。

12.HDU1241 Oil Deposits[DFS]

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Description:

The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil. A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to determine how many different oil deposits are contained in a grid.

Input:

The input file contains one or more grids. Each grid begins with a line containing m and n, the number of rows and columns in the grid, separated by a single space. If m = 0 it signals the end of the input; otherwise 1 <= m <= 100 and 1 <= n <= 100. Following this are m lines of n characters each (not counting the end-of-line characters). Each character corresponds to one plot, and is either ‘*’, representing the absence of oil, or ‘@’, representing an oil pocket.

Output:

For each grid, output the number of distinct oil deposits. Two different pockets are part of the same oil deposit if they are adjacent horizontally, vertically, or diagonally. An oil deposit will not contain more than 100 pockets.

Sample Input:

1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5 
****@
*@@*@
*@**@
@@@*@
@@**@
0 0 

Sample Output:

0
1
2
2

代码

1.DFS code:

#include<queue>
#include<iostream>
#include<string>
#include<cstring>using namespace std;const int N=105;
char g[N][N];
int n,m;
int dx[]={1,1,1,-1,-1,-1,0,0};
int dy[]={0,1,-1,0,1,-1,1,-1};
void dfs(int x,int y)
{for(int i=0;i<8;i++){int a=x+dx[i],b=y+dy[i];if(a<0||b<0||a>=n||b>=m||g[a][b]!='@')continue;g[a][b]='*';dfs(a,b);}return;
}
int main()
{while(~scanf("%d%d",&n,&m)&&(n||m)){for(int i=0;i<n;i++)scanf("%s",&g[i]);int cnt=0;for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(g[i][j]=='@'){g[i][j]='*';dfs(i,j);cnt++;}cout<<cnt<<endl;}return 0;
}

2.BFS code(自己写的，由于最近VJ进不去不知道对不对，仅供参考):

#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
int m,n,ans=0;
int dx[]={0,0,1,-1,-1,1,1,-1},dy[]={1,-1,0,0,-1,1,-1,1};
string s[105];
struct node{int x,y;
}; 
int main()
{while(cin>>m>>n){ans=0;if(m==0||n==0) return 0;for(int i=0;i<m;i++)cin>>s[i];for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(s[i][j]=='@'){queue<node> q;q.push({i,j});s[i][j]='*';while(q.size()){node t=q.front();q.pop();for(int i=0;i<8;i++){int x=t.x+dx[i];int y=t.y+dy[i];if(x>=0&&x<m&&y>=0&&y<n&&s[x][y]=='@'){q.push({x,y});s[x][y]='*';}}}ans++;				}}}cout<<ans<<"\n";}return 0;
}

自己的想法

这道题可以用DFS做。就是遍历循环，判断当前的位置是否为‘@’，是就ans++,将当前位置改为’*‘，再DFS搜索，在DFS里面再进行判断当前位置是否为’@'，循环上述操作，但不要ans++就行。这里要注意的是方向是8个，斜边也要算上。
这道题感觉也可以用BFS来做，方法差不多，就是用BFS来实现上面的操作，由于最近VJ进不去不知道是否正确。

13.HDU1495 非常可乐[BFS/数学]

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Description:

大家一定觉的运动以后喝可乐是一件很惬意的事情，但是seeyou却不这么认为。因为每次当seeyou买了可乐以后，阿牛就要求和seeyou一起分享这一瓶可乐，而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子，它们的容量分别是N 毫升和M 毫升 可乐的体积为S （S<101）毫升　(正好装满一瓶) ，它们三个之间可以相互倒可乐 (都是没有刻度的，且 S==N+M，101＞S＞0，N＞0，M＞0) 。聪明的ACMER你们说他们能平分吗？如果能请输出倒可乐的最少的次数，如果不能输出"NO"。

Input:

三个整数 : S 可乐的体积 , N 和 M是两个杯子的容量，以"0 0 0"结束。

Output:

如果能平分的话请输出最少要倒的次数，否则输出"NO"。

Sample Input:

7 4 3
4 1 3
0 0 0

Sample Output:

NO
3

代码

1.BFS code:

#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,s;
struct node{int n,m,s,t;
}st;
bool vis[105][105];
int bfs()
{queue<node> q;memset(vis,0,sizeof(vis));st.n=0,st.m=0,st.s=s,st.t=0;vis[n][m]=1;q.push(st);while(q.size()){node u=q.front(),v;q.pop();if(u.s==s/2&&u.n==s/2)//平分的条件是可乐杯只剩一半，另一半在大号杯 {return u.t;}if(u.s&&u.n!=n)//s->n{int a=n-u.n;if(u.s>=a) v.s=u.s-a,v.n=n;else v.s=0,v.n=u.n+u.s;v.m=u.m,v.t=u.t+1;if(!vis[v.n][v.m]){q.push(v);vis[v.n][v.m]=1;}}if(u.s&&u.m!=m)//s->m{int a=m-u.m;if(u.s>=a) v.s=u.s-a,v.m=m;else v.s=0,v.m=u.m+u.s;v.n=u.n,v.t=u.t+1;if(!vis[v.n][v.m]){q.push(v);vis[v.n][v.m]=1;}}if(u.n&&u.s!=s)//n->s{int a=s-u.s;if(u.n>=a) v.n=u.n-a,v.s=s;else v.n=0,v.s=u.n+u.s;v.m=u.m,v.t=u.t+1;if(!vis[v.n][v.m]){q.push(v);vis[v.n][v.m]=1;}}if(u.n&&u.m!=m)//n->m{int a=m-u.m;if(u.n>=a) v.n=u.n-a,v.m=m;else v.n=0,v.m=u.n+u.m;v.s=u.s,v.t=u.t+1;if(!vis[v.n][v.m]){q.push(v);vis[v.n][v.m]=1;}}if(u.m&&u.s!=s)//m->s{int a=s-u.s;if(u.m>=a) v.m=u.m-a,v.s=s;else v.m=0,v.s=u.m+u.s;v.n=u.n,v.t=u.t+1;if(!vis[v.n][v.m]){q.push(v);vis[v.n][v.m]=1;}}if(u.m&&u.n!=n)//m->n{int a=n-u.n;if(u.m>=a) v.m=u.m-a,v.n=n;else v.m=0,v.n=u.m+u.n;v.s=u.s,v.t=u.t+1;if(!vis[v.n][v.m]){q.push(v);vis[v.n][v.m]=1;}}}return 0; 
}
int main()
{while(cin>>s>>m>>n){if(s==0) break;if(s%2) {cout<<"NO\n";continue;}if(n<m) swap(n,m);//n做大号杯int ans=bfs();if(ans) cout<<ans<<"\n";else cout<<"NO\n"; }return 0;
}

2.数学 code:

#include<iostream>
using namespace std;
int a,b,c;
int gcd(int a,int b)
{return b?gcd(b,a%b):a;
}
int main()
{while(~scanf("%d%d%d",&a,&b,&c)&&(a||b||c)){a/=gcd(b,c);if(a&1)puts("NO");else printf("%d\n",a-1);}return 0;
}

自己的想法：

一开始写这道题时，我理解错了平分的意思，在我看来只要可乐杯最后只剩下一半可乐，就达到平分的条件了，但事实上还要容量大的杯子也要有可乐杯的一半可乐，所以最后我以为可以找规律，写了很长时间找出了我自以为对的规律，结果错了，害。这道题的第一种解法可以用BFS+模拟来做，每一次倒可乐时有6种倒法，分别为s->n,s->m,n->s,n->m,m->s,m->n，就根据这种倒法就可以用BFS写出来了。第二种解法是用数学，这种解法有点难理解，可以参考我下面给的链接。
第一种解法.
第二种解法.

14.HDU2612 Find a way[BFS]

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Description:

Pass a year learning in Hangzhou, yifenfei arrival hometown Ningbo at finally. Leave Ningbo one year, yifenfei have many people to meet. Especially a good friend Merceki.
Yifenfei’s home is at the countryside, but Merceki’s home is in the center of city. So yifenfei made arrangements with Merceki to meet at a KFC. There are many KFC in Ningbo, they want to choose one that let the total time to it be most smallest.
Now give you a Ningbo map, Both yifenfei and Merceki can move up, down ,left, right to the adjacent road by cost 11 minutes.

Input

The input contains multiple test cases.
Each test case include, first two integers n, m. (2<=n,m<=200).
Next n lines, each line included m character.
‘Y’ express yifenfei initial position.
‘M’ express Merceki initial position.
‘#’ forbid road;
‘.’ Road.
‘@’ KCF

Output

For each test case output the minimum total time that both yifenfei and Merceki to arrival one of KFC.You may sure there is always have a KFC that can let them meet.

Sample Input:

4 4
Y.#@
....
.#..
@..M
4 4
Y.#@
....
.#..
@#.M
5 5
Y..@.
.#...
.#...
@..M.
#...#

Sample Output :

66
88
66

代码

#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
char map[205][205];//地图int st[205][205];
bool vis[205][205];
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};int n,m;
struct node{int x,y,t;
};
void bfs(int x,int y)
{queue<node> q;q.push({x,y,0});memset(vis,0,sizeof(vis));vis[x][y]=1;while(!q.empty()){node u=q.front();q.pop();if(map[u.x][u.y]=='@'){st[u.x][u.y]+=u.t;}for(int i=0;i<4;i++){int xx=u.x+dx[i];int yy=u.y+dy[i];if(map[xx][yy]!='#'&&0<=xx&&xx<n&&0<=yy&&yy<m&&!vis[xx][yy]){q.push({xx,yy,u.t+1});vis[xx][yy]=1;				}}}}
int main()
{while(cin>>n>>m){memset(st,0,sizeof(st));int Yx,Yy,Mx,My;for(int i=0;i<n;i++){cin>>map[i];}for(int i=0;i<n;i++)for(int j=0;j<m;j++){if(map[i][j]=='Y'){Yx=i;Yy=j;}else if(map[i][j]=='M'){Mx=i;My=j;}}bfs(Yx,Yy);bfs(Mx,My);int ans=0x3f3f3f3f;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(st[i][j]){ans=min(ans,st[i][j]);}}}cout<<ans*11<<"\n";}return 0;
}

自己的想法

这道题我debug了很长时间，一直没有输出结果，让我非常纳闷。之后我就参考了别人的代码，根据别人的代码一步步改，改到能出结果为止。后来才发现是我输入有问题。一开始我定义了string map[205]，而不是char g[205][205],导致我一直无法输出结果，我也不知道为什么这种定义输入不行。好了，开始说正确解法了，这道题用了两次BFS，在BFS时要小心一个点，那就是当判断终止条件时，即：

if(map[u.x][u.y]=='@'){st[u.x][u.y]+=u.t;}

不要加continue!这个一定不能加，加了就错了。毕竟’@'不止一个。
参考链接.