73 条题解
-
1
Sky1231 (sky1231) LV 10 @ 2017-08-01 15:25:53
#include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iomanip> #include <iostream> #include <algorithm> #include <vector> #include <deque> #include <limits> #include <string> #include <sstream> using namespace std; const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f; int n,m,t,x,y,s_i,s_j,m_i,m_j; int d[25+1][25+1]; int v[25+1][25+1]; deque<int> q_i; deque<int> q_j; char a[25+1][25+1]; int main() { while (~scanf("%d%d%d",&t,&x,&y)) { m=x,n=y; for (int i=1;i<=n;i++) { char c; scanf("%c",&c); for (int j=1;j<=m;j++) { scanf("%c",&a[i][j]); if (a[i][j]=='s') a[i][j]='.',s_i=i,s_j=j; else if (a[i][j]=='m') a[i][j]='.',m_i=i,m_j=j; } } int mov_i[4]={-1,0,0,1}; int mov_j[4]={0,-1,1,0}; memset(d,oo_max,sizeof(d)); memset(v,0,sizeof(v)); for (d[s_i][s_j]=0,v[s_i][s_j]=1,q_i.resize(0),q_j.resize(0),q_i.push_back(s_i),q_j.push_back(s_j);(!q_i.empty())&&(!q_j.empty());v[q_i.front()][q_j.front()]=0,q_i.pop_front(),q_j.pop_front()) { int now_i=q_i.front(),now_j=q_j.front(); for (int i=0;i<4;i++) { int next_i=now_i+mov_i[i],next_j=now_j+mov_j[i]; if (1<=next_i&&next_i<=n&&1<=next_j&&next_j<=m&&a[next_i][next_j]!='o'&&d[now_i][now_j]+((a[next_i][next_j]=='#')?2:1)<d[next_i][next_j]) { d[next_i][next_j]=d[now_i][now_j]+((a[next_i][next_j]=='#')?2:1); if (v[next_i][next_j]==0) v[next_i][next_j]=1,q_i.push_back(next_i),q_j.push_back(next_j); } } } printf("%d\n",((d[m_i][m_j]<t)?d[m_i][m_j]:55555)); } }-
很H2O的题
-
-
0
最短路径，去屎吧！
BFS秒杀！
因为这个图中权值只有1和2两种可能，所以我们在搜到所有权值是2的点的时候在队列里面打一个标记，表示这个格子走的比较慢，等一轮才能扩展子节点。如果当前节点有个标记，那就把它直接出队，再入队，但是消掉它的标记。因为这个节点再入队以后的位置正好是当前的节点的子节点的位置，所以到达的时间都比这一段到达时间多1。因为这个有标记的节点在被检查到的时候，这个节点附近的节点时间是这个节点的前驱被扩展到的时间+1，所以这样放回队尾一次以后，它被处理的时间是他被发现的时间+2，正好是草地的通过时间。其实对于权值随意的图，也可以用这个方法，但是标记用一个正整数来表示它还要放回队尾的次数，被发现的时候就是发现它的节点的边权。这个方法的时间复杂度是O（最大边权*（V+E）），这个图里面最大边权固定，所以是O（V+E）。这个方法在权是整数，并且普遍很小的时候有用。program P1340;
type
tLoc=record
x,y,flag:integer;
end;
const
toward:array[1..4,1..2] of integer=((0,1),(0,-1),(1,0),(-1,0));
var
queue:array[1..10000] of tLoc;
top,tail:integer;
map:array[1..25,1..25] of char;
time:array[1..25,1..25] of integer;
height,length,melt:integer;
i,j:integer;
a,b:integer;
begin
readln(melt);
readln(length);
readln(height);
for i:=1 to height do
begin
for j:=1 to length do
begin
read(map[i,j]);
if map[i,j]='s' then
begin
time[i,j]:=0;
a:=i;
b:=j;
end
else
begin
time[i,j]:=-1;
end;
end;
readln;
end;
top:=2;
tail:=1;
queue[1].x:=a;
queue[1].y:=b;
queue[1].flag:=0;
while (top>tail) and (map[queue[tail].x,queue[tail].y]<>'m') do
begin
with queue[tail] do
begin
if flag>0 then
begin
queue[top].flag:=0;
queue[top].x:=x;
queue[top].y:=y;
inc(top);
inc(tail);
continue;
end;
for i:=1 to 4 do
begin
if ((x+toward[i,1]>=1) and (x+toward[i,1]<=height))and((y+toward[i,2]>=1) and (y+toward[i,2]<=length)) then
begin
if (time[x+toward[i,1],y+toward[i,2]]=-1) and (map[x+toward[i,1],y+toward[i,2]]<>'o') then
begin
queue[top].x:=x+toward[i,1];
queue[top].y:=y+toward[i,2];
if map[x+toward[i,1],y+toward[i,2]]='#' then
begin
queue[top].flag:=1;
end
else
begin
queue[top].flag:=0;
end;
if map[x,y]='#' then
begin
time[x+toward[i,1],y+toward[i,2]]:=time[x,y]+2;end
else
begin
time[x+toward[i,1],y+toward[i,2]]:=time[x,y]+1;
end;
inc(top);
end;
end;
end;
end;
inc(tail);
end;
if map[queue[tail].x,queue[tail].y]<>'m' then
begin
writeln('55555');
end
else
begin
if time[queue[tail].x,queue[tail].y]>=melt then
begin
writeln('55555');
end
else
begin
writeln(time[queue[tail].x,queue[tail].y]);
end;
end;
end. -
0
SPFA大爱
构图别写错了....Code
const int INF=(1<<28)-1;
struct edge
{
int in;
edge*nxt;
}pool[8000];
edge*et=pool;
edge*eds[1000];
void addedge(int a,int b)
{ et->in=b; et->nxt=eds[a]; eds[a]=et++; }
#define FOREACH_EDGE(i,j) for(edge*i=eds[j];i;i=i->nxt)int n;
char M[1000];
int d[1000];int st,ed;
int dist[1000];
int qh,qt;
int q[2000000];
int SPFA()
{
fillarray(dist,INF,n);qh=qt=0;
q[qt++]=st;
dist[st]=0;
d[st]=0;
d[ed]=1;
while(qh!=qt)
{
int&cur=q[qh];
FOREACH_EDGE(i,cur)
if( M[i->in]!='o' && dist[i->in] > dist[cur] + d[i->in])
{
dist[i->in]=dist[cur]+d[i->in];
q[qt++]=i->in;
}
qh++;
}return dist[ed];
}#define POINT(i,j) (((i)*yl)+(j))
int tlim;
int xl,yl;int main()
{
tlim=getint();
yl=getint();
xl=getint();
n=xl*yl;for(int i=0;i<xl;i++)
scanf("%s",M+i*yl);for(int i=0;i<xl;i++)
for(int j=0;j<yl;j++)
{
if(i>0) addedge(POINT(i,j),POINT(i-1,j));
if(j>0) addedge(POINT(i,j),POINT(i,j-1));
if(i<xl-1) addedge(POINT(i,j),POINT(i+1,j));
if(j<yl-1) addedge(POINT(i,j),POINT(i,j+1));if(M[POINT(i,j)]=='m') st=POINT(i,j);
if(M[POINT(i,j)]=='s') ed=POINT(i,j);
if(M[POINT(i,j)]=='.') d[POINT(i,j)]=1;
if(M[POINT(i,j)]=='#') d[POINT(i,j)]=2;
}int res=SPFA();
if(tlim<=res) printf("55555\n");
else printf("%d\n",res);return 0;
} -
0
1049451037 LV 8 @ 2012-10-19 10:15:10
本来以为是dfs，就用dfs的思路写了，结果写出来竟然发现莫名其妙的写了个广搜。。rp++了~
-
0
BFS 不用判重 运算结束出解
要注意的是 '#'情况可能被后面的'.'所替代
Const
dx:array[1..4] of longint=(1,-1,0,0);
dy:array[1..4] of longint=(0,0,1,-1);
Var
mx,my,z,head,tail,n,x,y,i,j:longint;
g:array[1..25,1..25] of char;
f:array[0..62500,1..2] of longint;
h:array[1..25,1..25] of longint;
function pp(a,b:longint):boolean;
begin
if (a>0) and (a0) and (btail then inc(tail);
f[t,1]:=f[x,1]+dx[i];
f[t,2]:=f[x,2]+dy[i];
h[f[t,1],f[t,2]]:=h[f[x,1],f[x,2]]+k;
end;
end;
end;
end;
begin
LL_F(x);
while headtail do
begin
inc(head);
LL_F(head);
end;
end;
begin
readln(n);
readln(y);
readln(x);
z:=x*y;
for i:=1 to x do
begin
for j:=1 to y do
begin
read(g);
if g='s' then
begin f[1,1]:=i;f[1,2]:=j; g:='o';end else
if g='m' then
begin mx:=i;my:=j; end;
end;
readln;
end;
head:=1;tail:=1;
L_F(1);
wri(h[mx,my]);
end. -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0msvar t,m,n,i,j,min:longint;
a:array[0..26,0..27]of char;
used:array[0..26,0..26]of boolean;
dx:array[1..4]of integer=(1,0,-1,0);
dy:array[1..4]of integer=(0,1,0,-1);
f:array[0..26,0..26]of longint;
procedure find(dep,x,y:longint);
var i:longint;
begin
if dep>=t then exit;
if (a[x,y]='m') then
begin
if depdep+1) then
begin
used[x+dx[i],y+dy[i]]:=true;
f[x+dx[i],y+dy[i]]:=dep+1;
find(dep+1,x+dx[i],y+dy[i]);
used[x+dx[i],y+dy[i]]:=false;
end
else if (a[x+dx[i],y+dy[i]]='#')and(f[x+dx[i],y+dy[i]]>dep+2) then
begin
used[x+dx[i],y+dy[i]]:=true;
f[x+dx[i],y+dy[i]]:=dep+2;
find(dep+2,x+dx[i],y+dy[i]);
used[x+dx[i],y+dy[i]]:=false;
end
end;
end;
begin
readln(t);
readln(m);
readln(n);
for i:=0 to n+1 do
for j:=0 to m+1 do
begin
used:=true;
f:=99999999;
end;
for i:=1 to n do
begin
for j:=1 to m do
begin
read(a);
used:=false;
end;
readln;
end;
min:=99999999;
for i:=1 to n do
for j:=1 to m do
if a='s' then
begin
used:=true;
find(0,i,j);
if min=99999999 then writeln(55555)
else writeln(min);
halt;
end;end.
DFS.本只得20分.但看楼下题解优化后便秒杀
-
0
sinbking11 LV 8 @ 2009-10-30 14:03:31
小弟不才果然牛逼；
膜拜神牛；
这都ac了；
~~~~
水啊水啊 -
0
小弟果然不才，水题做了好久。
bfs enough，简单搜，别搞复杂的，小弟做人就追求简单
不说了，电脑流水了
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms const d1:array[1..4] of integer=(0,1,0,-1);
d2:array[1..4] of integer=(1,0,-1,0);
type date=record
m,n,c:integer;
end;
var map:array[0..26,0..26] of integer;
i,j,ans,x,y,q1,q2,t:integer;
q:array[0..700] of date;
procedure init;
var i,j:integer;
ch:char;
begin readln(x,y);
for i:=0 to 26 do
for j:= 0 to 26 do
map:=0;
for i:=1 to y do
begin for j:=1 to x do
begin read(ch);
if (ch='s') or ( ch='S') then begin q1:=i;q2:=j; end;
if (ch='m') then map:=3;
if ch='.' then map:=1;
if ch='#' then map:=2;
end;
readln;
end;
end;procedure bfs;
var top,rear,i:integer;
flag:boolean;
begin top:=1; rear:=1; q[1].m:=q1; q[1].n:=q2; q[1].c:=0; flag:=false;
while top=1) and(q[top].m+d1[i]=1) and (q[top].n+d2[i]=1) and(q[top].m+d1[i]=1) and (q[top].n+d2[i] -
0
SecretAgent LV 10 @ 2009-10-26 19:30:57
把地图转换成一张无向图，
对于道路和起点，出度为1
对于草地，出度为2
对于障碍和终点，出度为无限大接下来求一次单源最短路即可
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
数据好弱，很普通的BFS就秒了，可惜没加等号unac了几次
const
dx:array[1..4]of longint=(-1,0,1,0);
dy:array[1..4]of longint=(0,1,0,-1);type
sate=record
x,y:longint;
special:boolean;
step:longint;
pre:longint;
end;var
temp:string;
min,t,tm,x,y,i,j,k,head,tail,x1,y1,l,r:longint;
a:array[1..100000]of sate;
m:array[1..25,1..25]of char;
b:array[1..25,1..25]of boolean;
c:array[1..100]of longint;begin
tm:=0;
fillchar(b,sizeof(b),true);
readln(t);
readln(x);
readln(y);
for i:=1 to y do
begin
readln(temp);
for j:=1 to x do
begin
m[j,i]:=temp[j];
if m[j,i]='s' then
begin
x1:=j;
y1:=i;
end;
end;
end;
b[x1,y1]:=false;
a[1].x:=x1;
a[1].y:=y1;
a[1].step:=0;
a[1].special:=false;
a[1].pre:=0;
head:=0;
tail:=1;
repeat
inc(head);
if a[head].special then
begin
inc(tail);
a[tail].x:=a[head].x;
a[tail].y:=a[head].y;
a[tail].step:=a[head].step+1;
a[tail].special:=false;
a[tail].pre:=a[head].pre;
end
else
for i:=1 to 4 do
begin
l:=dx[i]+a[head].x;
r:=dy[i]+a[head].y;
if(l>0)and(r>0)and(l -
0
嘢 一次秒杀
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms话说 暴力永远是解决问题的好办法啊啊哈O(∩_∩)O哈！
就是不知道我这个带着有点儿记忆化的搜索算不算暴力啊
program p1340;
var n,m,t,i,j,x0,y0,xi,yi:longint;
ch:char;
a:array[1..4,0..1] of integer;
f,tim:array[0..30,0..30] of longint;procedure search(xt,yt:longint);
var r:longint;
begin
if (xt=xi)and(yt=yi) then exit
else
for r:=1 to 4 do
if f[xt,yt]+tim[xt+a[r,0],yt+a[r,1]]f[xi,yi] then writeln(f[xi,yi])
else writeln(55555);
end.
Sky1231 (sky1231)
LV 10
@ 2017-08-01 15:25:53
