2019.3.7 kuangbin训练 UVA11624 POJ3984 HDU1241 HDU1495 HDU1612
UVA11624
队列中先加火再加人，node中state=0是人走过的格子，state=1是火走过的格子
坑点：
可能有多处火
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn=1e6;
int T,N,M;
char m[1007][1007];
struct node
{
int x,y,step,state;
node(int xx=0,int yy=0,int ss=0,int st=0)
{
x=xx;y=yy;step=ss;state=st;
}
};
node J,F[maxn+7];
int cnt;// num of F
int vis[1007][1007];
int X[]={-1,0,1,0};
int Y[]={0,1,0,-1};
int ans;
void bfs()
{
queue<node> q;
while(!q.empty()) q.pop();
for(int i=0;i<cnt;i++)
{
q.push(F[i]);
vis[F[i].x][F[i].y]=1;
}
q.push(J);
vis[J.x][J.y]=1;
while(!q.empty())
{
node temp=q.front();
q.pop();
if((temp.x==0 || temp.x==N-1 || temp.y==0 || temp.y==M-1)&& temp.state==0 )
{
ans=temp.step;
return;
}
for(int i=0;i<4;i++)
{
int nx=temp.x+X[i];
int ny=temp.y+Y[i];
if(nx<0 || nx>=N || ny<0 || ny>=M)
continue;
if(!vis[nx][ny] && m[nx][ny]=='.')
{
vis[nx][ny]=1;
q.push(node(nx,ny,temp.step+1,temp.state));
}
}
}
}
int main()
{
scanf("%d",&T);
while(T--)
{
ans=-1;
cnt=0;
memset(vis,0,sizeof(vis));
scanf("%d %d",&N,&M);
for(int i=0;i<N;i++)
{
scanf("%s",m[i]);
for(int j=0;j<M;j++)
{
if(m[i][j]=='J')
{
J.x=i;
J.y=j;
J.step=0;
J.state=0;
}
if(m[i][j]=='F')
{
F[cnt].x=i;
F[cnt].y=j;
F[cnt].step=0;
F[cnt].state=1;
cnt++;
}
}
}
bfs();
if(ans==-1)
printf("IMPOSSIBLE\n");
else printf("%d\n",ans+1);
}
return 0;
}
poj3984
水题，bfs，pre的用法之前写过
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn=1e5+7;
int m[5][5],vis[5][5];
int n=5;
int X[]={-1,0,1,0};
int Y[]={0,1,0,-1};
struct node
{
int x,y;
node (int xx=0,int yy=0)
{
x=xx;y=yy;
}
};
node pre[5][5];
void bfs()
{
queue<node> q;
while(!q.empty()) q.pop();
q.push(node(0,0));
vis[0][0]=1;
pre[0][0]=node(-1,-1);
while(!q.empty())
{
node temp=q.front();
q.pop();
if(temp.x==n-1 && temp.y==n-1)
break;
for(int i=0;i<4;i++)
{
int nx=temp.x+X[i];
int ny=temp.y+Y[i];
if(nx<0 || nx>=n || ny<0 || ny>=5)
continue;
if(!vis[nx][ny] && m[nx][ny]==0)
{
vis[nx][ny]=1;
pre[nx][ny]=temp;
q.push(node(nx,ny));
}
}
}
}
void print(int x,int y)
{
if(x==-1 && y==-1)
return;
print(pre[x][y].x,pre[x][y].y);
printf("(%d, %d)\n",x,y);
}
int main()
{
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d",&m[i][j]);
bfs();
print(4,4);
return 0;
}
hdu1241
水题，dfs，8个方向
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn=1e5+7;
int n,m;
char maze[107][107];
int X[]={-1,-1,0,1,1,1,0,-1};
int Y[]={0,1,1,1,0,-1,-1,-1};
int ans;
void dfs(int x,int y)
{
maze[x][y]='*';
for(int i=0;i<8;i++)
{
int nx=x+X[i];
int ny=y+Y[i];
if(nx<0 || nx>=n || ny<0 || ny>=m)
continue;
if(maze[nx][ny]=='@')
dfs(nx,ny);
}
}
int main()
{
while(scanf("%d %d",&n,&m)!=EOF && (n+m))
{
ans=0;
for(int i=0;i<n;i++)
scanf("%s",maze[i]);
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
if(maze[i][j]=='@')
{
dfs(i,j);
ans++;
}
}
printf("%d\n",ans);
}
return 0;
}
hdu1495
bfs，模拟6种倒水方式
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn=1e5+7;
int N,M,S;
int vis[107][107][107];
int ans,ansS,ansN,ansM;
struct node
{
int s,n,m,step;
node(int ss,int nn,int mm,int st)
{
n=nn;m=mm;s=ss;step=st;
}
};
void bfs()
{
queue<node> q;
while(!q.empty()) q.pop();
q.push(node(S,0,0,0));
vis[S][0][0]=1;
while(!q.empty())
{
node temp=q.front();
q.pop();
//printf("(%d %d %d %d)\n",temp.s,temp.n,temp.m,temp.step);
if(temp.s==S/2 || temp.n==S/2 || temp.m==S/2)
{
ans=temp.step;
ansS=temp.s;
ansN=temp.n;
ansM=temp.m;
break;
}
//S->N
if(temp.s+temp.n>N)
{
if(!vis[temp.s+temp.n-N][N][temp.m])
{
vis[temp.s+temp.n-N][N][temp.m]=1;
q.push(node(temp.s+temp.n-N,N,temp.m,temp.step+1));
}
}
else
{
if(!vis[0][temp.s+temp.n][temp.m])
{
vis[0][temp.s+temp.n][temp.m]=1;
q.push(node(0,temp.s+temp.n,temp.m,temp.step+1));
}
}
//S->M
if(temp.s+temp.m>M)
{
if(!vis[temp.s+temp.m-M][temp.n][M])
{
vis[temp.s+temp.m-M][temp.n][M]=1;
q.push(node(temp.s+temp.m-M,temp.n,M,temp.step+1));
}
}
else
{
if(!vis[0][temp.n][temp.s+temp.m])
{
vis[0][temp.n][temp.s+temp.m]=1;
q.push(node(0,temp.n,temp.s+temp.m,temp.step+1));
}
}
//N->S
if(!vis[temp.s+temp.n][0][temp.m])
{
vis[temp.s+temp.n][0][temp.m]=1;
q.push(node(temp.s+temp.n,0,temp.m,temp.step+1));
}
//M->S
if(!vis[temp.s+temp.m][temp.n][0])
{
vis[temp.s+temp.m][temp.n][0]=1;
q.push(node(temp.s+temp.m,temp.n,0,temp.step+1));
}
//N->M
if(temp.n+temp.m>M)
{
if(!vis[temp.s][temp.n+temp.m-M][M])
{
vis[temp.s][temp.n+temp.m-M][M]=1;
q.push(node(temp.s,temp.n+temp.m-M,M,temp.step+1));
}
}
else
{
if(!vis[temp.s][0][temp.n+temp.m])
{
vis[temp.s][0][temp.n+temp.m]=1;
q.push(node(temp.s,0,temp.n+temp.m,temp.step+1));
}
}
//M->N
if(temp.n+temp.m>N)
{
if(!vis[temp.s][N][temp.n+temp.m-N])
{
vis[temp.s][N][temp.n+temp.m-N]=1;
q.push(node(temp.s,N,temp.n+temp.m-N,temp.step+1));
}
}
else
{
if(!vis[temp.s][temp.n+temp.m][0])
{
vis[temp.s][temp.n+temp.m][0]=1;
q.push(node(temp.s,temp.n+temp.m,0,temp.step+1));
}
}
}
}
int main()
{
while(scanf("%d %d %d",&S,&N,&M)!=EOF && (S+N+M))
{
if(S%2)
{
printf("NO\n");
continue;
}
memset(vis,0,sizeof(vis));
ans=-1;
bfs();
if(ans==-1)
printf("NO\n");
else
{
if(!ansS || !ansN || !ansM)
printf("%d\n",ans);
else printf("%d\n",ans+1);
}
}
return 0;
}
