两天肝完
感觉自己的暴力水平上升了
码力大仙！！！

A.POJ1321 棋盘问题

有一个坑点就是可能相邻层没有棋盘，所以直接搜全部

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
int n,m;
int dx[]={0,1,1,1,-1,-1,-1,0,0};
int dy[]={0,1,-1,0,1,-1,0,1,-1};
char a[15][15];
int zx[1005];
int zy[1005],vis[1005];
int t[20][20];
int ans;
void fuck(); 
void dfs(int x,int num){
	if(num==0){
		ans++;
		return;
	}
	for(int i=x;i<n;i++){
		for(int j=0;j<n;j++){
			if(a[i][j]=='#'&&vis[j]==0){
				vis[j]=1;
				dfs(i+1,num-1);
				vis[j]=0;
			}
		}
	}
	return;
}
int main(){
	while(scanf("%d%d",&n,&m)){
		if(n==-1&&m==-1)break;
		for(int i=0;i<n;i++){
			scanf("%s",&a[i]);
		}
		memset(vis,0,sizeof(vis));
		ans=0;
		dfs(0,m);
		cout<<ans<<endl;
	}
	return 0;
}

B.POJ 2251 Dungeon Master

裸三维BFS，没有坑点
就是POJ很神奇，把bfs过程直接暴力就让我MLE？
让我学会了能不写在主函数里就一定写外面

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
int n,m,k;
char a[35][35][35];
int vis[35][35][35];
int ans;
int sx,sy,sz,zx,zy,zz;
int base[6][3] = { {-1,0,0},{1,0,0},{0,-1,0},{0,1,0},{0,0,-1},{0,0,1} };
struct node{
	int x,y,z,bu;
	friend bool operator<(node a,node b)
    {
        return a.bu>b.bu;
    }
};
bool zou(int x,int y,int z){
	if(x<1||x>k)return false;
	if(y<1||y>m)return false;
	if(z<1||z>n)return false;
	return true;
}
int main(){
	while(scanf("%d%d%d",&n,&m,&k)){
		if(n==0&&m==0&&k==0)break;
		int fa=0;
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				for(int t=1;t<=k;t++){
					cin>>a[t][j][i];
					if(a[t][j][i]=='S'){
						sx=t;
						sy=j;
						sz=i;
					}
					if(a[t][j][i]=='E'){
						zx=t;
						zy=j;
						zz=i;
						a[t][j][i]='.';
					}
				}
			}
		}
		priority_queue<node>q;
		q.push((node){sx,sy,sz,0});
		while(!q.empty()){
			node x=q.top();
			q.pop();
			if(x.x==zx&&x.y==zy&&x.z==zz){
				printf("Escaped in %d minute(s).\n",x.bu);
				fa=1;
				break;
			}
			for(int i=0;i<6;i++){
				int xx=x.x+base[i][0];
				int yy=x.y+base[i][1];
				int zz=x.z+base[i][2];
				if(zou(xx,yy,zz)&&a[xx][yy][zz]!='#'&&vis[xx][yy][zz]==0){
					vis[xx][yy][zz]=1;
					q.push((node){xx,yy,zz,x.bu+1});
				}
			}
		}
		if(fa==0)printf("Trapped!\n");
	}
	return 0;
}

C.POJ 3278 Catch That Cow

一维BFS
控制好边界就行，纯手速秒杀题
（某秒因为边界RE了十多发）

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
int n,m,k;
int a[100005];
struct node
{
	int x,num;
};
int vis[100005];
int main(){
	cin>>n>>m;
	queue<node>q;
	q.push((node){n,0});
	vis[n]=1;
	while(!q.empty()){
		node x=q.front();
		q.pop();
		if(x.x==m){
			cout<<x.num;
			return 0;
		}
		if(x.x+1<=100000&&x.x+1>=0&&vis[x.x+1]==0){
			q.push((node){x.x+1,x.num+1});
			vis[x.x+1]=1;
		}
		if(x.x-1<=100000&&x.x-1>=0&&vis[x.x-1]==0){
			q.push((node){x.x-1,x.num+1});
			vis[x.x-1]=1;
		}
		if(x.x*2<=100000&&x.x*2>=0&&vis[x.x*2]==0){
			q.push((node){x.x*2,x.num+1});
			vis[x.x*2]=1;
		}
	}
	return 0;
}

D.POJ 3279 Fliptile

经典开关问题，让我第一次接触到了状态压缩hhh
如果会状压好像也就是个暴力了

#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std; 
int m,n;
int a[20][20],cal[20][20],out[20][20];
const int dx[]={0,0,1,-1,0};
const int dy[]={1,-1,0,0,0};
int zt(int x,int y){
	int temp=a[x][y];
	for(int i=0;i<5;i++){
		int xx=x+dx[i];
		int yy=y+dy[i];
		if(xx<1||yy<1||xx>n||yy>m)continue;
		temp+=cal[xx][yy];
	}
	return temp%2;
}
int dfs(){
	for(int i=2;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(zt(i-1,j)){
				cal[i][j]=1;
			}
		}
	}
	for(int i=1;i<=m;i++){
		if(zt(n,i))return -1;
	}
	int res=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			res+=cal[i][j];
		}
	}
	return res;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	int fa=0;
	int ans=0x3f3f3f3f;
	for(int i=0;i<1<<m;i++){
		memset(cal,0,sizeof(cal));
		for(int j=1;j<=m;j++){
			cal[1][m-j+1]=i>>(j-1)&1;
		}
		int c=dfs();
		if(c>=0&&c<ans){
			fa=1;
			ans=c;
			memcpy(out,cal,sizeof(cal));
		}
	}
	if(!fa)cout<<"IMPOSSIBLE"<<endl;
	else{
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(j!=1)cout<<" ";
				cout<<out[i][j];
			}
			cout<<endl;
		}
	}
	return 0;
}  

E.POJ 1426 Find The Multiple

思路就是直接暴力构造搜 *10 和 *10+1
判断是否能整除

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#define int long long
using namespace std;
int n,m,k,c;
void dfs(unsigned long long x,int t){
	if(t>19)return;
	if(c==1)return;
	if(x%n==0){
		cout<<x<<endl;
		c=1;
		return;
	}
	dfs(x*10,t+1);
	dfs(x*10+1,t+1);
	return;
}
signed main(){
	while(1){
		cin>>n;
		c=0;
		if(n==0)break;
		dfs(1,0);
	}
	return 0;
}

F.POJ 3126 Prime Path

一个有点意思的搜索，不过难度不大，思路就先跑一遍欧拉筛，然后写一个更换数字的函数，暴力循环判断是否为素数，加入队列中就ok了

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#define int long long
using namespace std;
int n,m,k,c;
int prime[10005];
bool sf[10005];
const int maxn=10005;
int vis[10005];
int cnt=1;
void sushu(){         
    int num=0;       
    memset(sf,true,sizeof(sf));
    for(int i=2;i<=maxn;i++){          
        if(sf[i]) prime[++num]=i;     
        for(int j=1;j<=num;j++){     
            if(i*prime[j]>maxn) break; 
            sf[i*prime[j]]=false;      
            if(i%prime[j]==0) break;   
        }
    }
    sf[1]=false;
    sf[0]=false;
}
int bian(int x,int t,int c){
	int ge,shi,bai,qian;
	ge=x%10;
	x/=10;
	shi=x%10;
	x/=10;
	bai=x%10;
	qian=x/=10;
	if(t==1)return c*1000+bai*100+shi*10+ge;
	else if(t==2)return qian*1000+c*100+shi*10+ge;
	else if(t==3)return qian*1000+bai*100+c*10+ge;
	else if(t==4)return qian*1000+bai*100+shi*10+c;
}
struct node{
	int x,num;
};
void bfs(int x){
	queue<node>q;
	q.push((node){x,0});
	vis[x]=1;
	while(!q.empty()){
		node u=q.front();
		q.pop();
		if(u.x==m){
			cout<<u.num<<endl;
			return;
		}
		for(int i=1;i<=4;i++){
			for(int j=0;j<=9;j++){
				if(i==4&&(j==2||j==4||j==6||j==8))continue;
				if(i==1&&j==0)continue;
				int tt=bian(u.x,i,j);
				if(sf[tt]==true&&vis[tt]==0){
					q.push((node){tt,u.num+1});
					vis[tt]=1;
				}
			}
		}
	}
}
signed main(){
	cin>>k;
	sushu();
// if(sf[50])cout<<"1";
// else cout<<"0";
	while(k--){
		cin>>n>>m;
		if(n==m){
			cout<<"0"<<endl;
			continue;
		}
		memset(vis,0,sizeof(vis));
		bfs(n);
	}
	return 0;
}

G.POJ 3087 Shuffle’m Up

傻逼题，难度不够，英语来凑，直接模拟就行

#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <map>
using namespace std; 
int n,c;
string a,b,de;
void dfs(int x){
	map<string,int>m;
	string t=a+b;
	int step=0;
	while(m[t]==0&&t!=de){
		int k=0;
		m[t]=1;
		step++;
		string str=t;
		for(int i=0;i<c;i++){
			str[k]=t[i+c];
			k++;
			str[k]=t[i];
			k++;
		}
		t=str;
	}
	if(t==de){
		cout<<x<<" "<<step<<endl;
	}
	else{
		cout<<x<<" "<<"-1"<<endl;
	}
}
int main(){
	cin>>n;
	int kk=0;
	while(n--){
		kk++;
		cin>>c;
		cin>>a>>b>>de;
		dfs(kk);
	}
	return 0;
}

H.POJ 3414 Pots

这题真的是个超级码力题
写完就感觉自己码力很猛
暴力判断八种情况，我这里开结构体里面放了一个数组表示第一和第二个杯子，并用vector来保存路径

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
using namespace std;
void fuck();
void shit();
int a,b,c,n,m;
bool vis[102][102];
struct node{
	int w[2],num;
	vector<string>v;
};
int fill(int x,int c){
	return c;
}
int drop(int x){
	return 0;
}
void bfs(int x,int b,int c){
	node t;
	int fa=0;
	t.w[0]=0;
	t.w[1]=0;
	t.num=0;
	vis[0][0]=false;
	queue<node>q;
	q.push(t);
	while(!q.empty()){
		node t=q.front();
		q.pop();
		if(t.w[0]==c||t.w[1]==c){
			cout<<t.num<<endl;
			for(int i=0;i<t.v.size();i++){
				cout<<t.v[i]<<endl;
			}
			fa=1;
			return;
		}
		if(vis[fill(1,a)][t.w[1]]==true){
			vis[fill(1,a)][t.w[1]]=false;
			node a=t;
			a.w[0]=fill(1,x);
			a.num++;
			a.v.push_back("FILL(1)");
			q.push(a);
		}
		if(vis[t.w[0]][fill(2,b)]==true){
			vis[t.w[0]][fill(2,b)]=false;
			node a=t;
			a.w[1]=fill(2,b);
			a.num++;
			a.v.push_back("FILL(2)");
			q.push(a);
		}
		if(vis[0][t.w[1]]==true){
			vis[0][t.w[1]]=false; 
			node a=t;
			a.w[0]=0;
			a.num++;
			a.v.push_back("DROP(1)");
			q.push(a);
		}
		if(vis[t.w[0]][0]==true){
			vis[t.w[0]][0]=false;
			node a=t;
			a.w[1]=0;
			a.num++;
			a.v.push_back("DROP(2)");
			q.push(a);
		}
		if(t.w[0]+t.w[1]>b){
			int cha=t.w[0]+t.w[1]-b;
			if(vis[cha][b]==true){
				vis[cha][b]=false;
				node a=t;
				a.w[0]=cha;
				a.w[1]=b;
				a.num++;
				a.v.push_back("POUR(1,2)");
				q.push(a);
			}
		}
		else{
			int cha=t.w[0]+t.w[1];
			if(vis[0][cha]==true){
				vis[0][cha]=false;
				node a=t;
				a.w[0]=0;
				a.w[1]=cha;
				a.num++;
				a.v.push_back("POUR(1,2)");
				q.push(a);
			}
		}
		if(t.w[0]+t.w[1]>x){
			int cha=t.w[0]+t.w[1]-x;
			if(vis[x][cha]==true){
				vis[x][cha]=false;
				node a=t;
				a.w[0]=x;
				a.w[1]=cha;
				a.num++;
				a.v.push_back("POUR(2,1)");
				q.push(a);
			}
		}
		else{
			int cha=t.w[0]+t.w[1];
			if(vis[cha][0]==true){
				vis[cha][0]=false;
				node a=t;
				a.w[0]=cha;
				a.w[1]=0;
				a.num++;
				a.v.push_back("POUR(2,1)");
				q.push(a);
			}
		}
	}
	if(!fa)cout<<"impossible";
	return;
}
int main(){
	cin>>a>>b>>c;
	memset(vis,true,sizeof(vis));
	bfs(a,b,c);
} 

I.FZU 2150 Fire Game

码力屑题，让我自闭了一下午，不想写

J.UVA 11624 Fire!

对火和人分别bfs，并记录时间，需要注意的坑点是可能有多团火，然后注意边界

#include<bits/stdc++.h>
using namespace std;
const int dx[4]={1,-1,0,0};
const int dy[4]={0,0,-1,1};
const int inf=99999999;
int vis[1505][1505],f[1505][1505];
char a[1505][1505];
int n,m,c,tt;
struct node{
	int x,y,t;
}gg;
int main(){
	int t;
	int sx,sy;
	cin>>t;
	while(t--){
		cin>>n>>m;
		c=0;
		queue<node>fire;
		queue<node>q;
		memset(vis,0,sizeof(vis));
		memset(a,'.',sizeof(a));
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cin>>a[i][j];
				f[i][j]=inf;
				if(a[i][j]=='J'){
					sx=i;
					sy=j;
				}
				if(a[i][j]=='F'){
					fire.push((node){i,j,0});
					vis[i][j]=1;
				}
			}
		}
		while(!fire.empty()){
			node s=fire.front();
			fire.pop();
			for(int i=0;i<4;i++){
				int xx=s.x+dx[i];
				int yy=s.y+dy[i];
				if(xx>=1&&yy>=1&&xx<=n&&yy<=m&&vis[xx][yy]==0&&a[xx][yy]=='.'){
					vis[xx][yy]=1;
					f[xx][yy]=s.t+1;
					fire.push((node){xx,yy,s.t+1});
				}
			}
		}
		memset(vis,0,sizeof(vis));
		q.push((node){sx,sy,0});
		vis[sx][sy]=1;
		while(!q.empty()){
			node s=q.front();
			q.pop();
			if((s.x<=1||s.y<=1||s.x>=n||s.y>=m)&&s.t<f[s.x][s.y]){
				c++;
				cout<<s.t+1<<endl;
				break;
			}
			for(int i=0;i<4;i++){
				int xx=s.x+dx[i];
				int yy=s.y+dy[i];
				if(xx>=1&&yy>=1&&xx<=n&&yy<=m&&vis[xx][yy]==0&&a[xx][yy]=='.'){
					vis[xx][yy]=1;
					q.push((node){xx,yy,s.t+1});
				}
			}
		}
		if(!c){
			cout<<"IMPOSSIBLE"<<endl;
		}
	}
}

K.POJ 3984 迷宫问题

弱智题

L.HDU 1241 Oil Deposits

问有多少个联通块
直接循环，dfs走过的点变为普通路，dfs的次数就是答案

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#define int long long
using namespace std;
int n,m,k,c;
int prime[10005];
bool sf[10005];
const int maxn=10005;
int vis[105][105];
char a[1005][1005];
const int dx[]={1,1,1,-1,-1,-1,0,0};
const int dy[]={1,-1,0,1,-1,0,1,-1};
int cnt=1;
void dfs(int x,int y){
	for(int i=0;i<8;i++){
		int xx=x+dx[i];
		int yy=y+dy[i];
		if(xx>=1&&yy>=1&&xx<=n&&yy<=m&&a[xx][yy]=='@'){
			a[xx][yy]='*';
			dfs(xx,yy);
		}
	}
	return;
}
signed main(){
	while(1){
		cin>>n>>m;
		int ans=0;
		if(n==0&&m==0)break;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cin>>a[i][j];
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(a[i][j]=='@'){
					a[i][j]='*';
					dfs(i,j);
		// a[i][j]='*';
					ans++;
				}
			}
		}
		cout<<ans<<endl;
	}
}

M.HDU 1495 非常可乐

又是一个码力屑题，纯暴力bfs
如果变量没写好可能容易自闭

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
int n,m,k,c;
int v[5];
struct node{
	int v[3],num;
	node(int x,int y,int z,int st){
		v[0]=x;
		v[1]=y;
		v[2]=z;
		num=st;
	}
};
bool vis[102][102][102];
const int d1[6] = {0, 0, 1, 1, 2, 2};
const int d2[6] = {1, 2, 0, 2, 0, 1};
void bfs(){
	queue<node>q;
	memset(vis,true,sizeof(vis));
	q.push(node{v[0],0,0,0});
	vis[v[0]][0][0]=false;
	while(!q.empty()){
			node x=q.front();
			q.pop();
			int cnt=0;
			int dd=v[0]/2;
			for(int i=0;i<3;i++){
				if(x.v[i]==dd){
					cnt++;
				}
				if(cnt>=2){
					cout<<x.num<<endl;
					return;
				}
			}
			for(int i=0;i<6;i++){
				node in=x;
				in.num++;
				if(x.v[d1[i]]){
					int cha=v[d2[i]]-x.v[d2[i]];
					if(cha>=x.v[d1[i]]){
						in.v[d2[i]]+=in.v[d1[i]];
						in.v[d1[i]]=0;
					}
					else{
						in.v[d1[i]]-=cha;
						in.v[d2[i]]+=cha;
					}
					if(vis[in.v[0]][in.v[1]][in.v[2]]==true){
						q.push(in);
						vis[in.v[0]][in.v[1]][in.v[2]]=false;
					}
				}
			}
		}
		printf("NO\n");
}
signed main(){
	while(scanf("%d%d%d",&v[0],&v[1],&v[2])){
		if(v[0]==0&&v[1]==0&&v[2]==0)break;
		if(v[0]%2==1){
			cout<<"NO"<<endl;
			continue;
		}
		bfs();
	}
	return 0;
}

N.HDU 2612 Find a way

跑两个bfs，记录两人到达每一个KFC的时间，最后循环求出最小时间（今晚刚吃KFC）

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
int n,m,k,c;
const int maxn=10005;
int vis[205][205];
int cnt,cnt1,cnt2;
char a[1005][1005];
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
struct node{
	int x,y,num;
};
int dis[205][205];
signed main(){
	while(scanf("%d%d",&n,&m)!=EOF){
		int ans=99999999;
		vector<int>v1,v2;
		c=0;
		if(n==0&&m==0)break;
		cnt=0,cnt1=0,cnt2=0;
		int sx1,sy1,sx2,sy2;
		memset(dis,0,sizeof(dis));
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cin>>a[i][j];
				vis[i][j]=0;
				if(a[i][j]=='Y'){
					sx1=i;
					sy1=j;
				}
				if(a[i][j]=='M'){
					sx2=i;
					sy2=j;
				}
				if(a[i][j]=='@'){
					v1.push_back(j);
					v2.push_back(i);
				}
			}
		}
		queue<node>q;
		q.push((node){sx1,sy1,0});
		vis[sx1][sy1]=1;
		while(!q.empty()){
			node x=q.front();
			q.pop();
			if(a[x.x][x.y]=='@'){
				dis[x.x][x.y]+=x.num;
			}
			for(int j=0;j<4;j++){
				int xx=dx[j]+x.x;
				int yy=dy[j]+x.y;
				if(xx>=1&&yy>=1&&xx<=n&&yy<=m&&vis[xx][yy]==0&&a[xx][yy]!='#'){
					vis[xx][yy]=1;
					q.push((node){xx,yy,x.num+1});
				}
			}
		}
		while(!q.empty()){
			q.pop();
		}
		memset(vis,0,sizeof(vis));
		q.push((node){sx2,sy2,0});
		vis[sx2][sy2]=1;
		while(!q.empty()){
			node x=q.front();
			q.pop();
			if(a[x.x][x.y]=='@'){
				dis[x.x][x.y]+=x.num;
			}
			for(int j=0;j<4;j++){
				int xx=dx[j]+x.x;
				int yy=dy[j]+x.y;
				if(xx>=1&&yy>=1&&xx<=n&&yy<=m&&vis[xx][yy]==0&&a[xx][yy]!='#'){
					vis[xx][yy]=1;
					q.push((node){xx,yy,x.num+1});
				}
			}
		}
		ans=99999999;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(dis[i][j]!=0)ans=min(ans,dis[i][j]);
			}
		}
		cout<<ans*11<<endl;
	}
}

虽然这个搜索专题难度不大但是码力是真的不小…
搜索（×）锻炼暴力水平（√）
下一个专题：最短路
加油！！！