1 条题解
-
0
C :
#include<stdio.h> #include<string.h> #define min(x,y) x>y?y:x int a,b,c,d,p; char map[103][103]; void dfs(int x,int y,int s) { if(map[x][y]=='#')return ; if(x==c && y==d ){p=min(s,p);return ;} s++; map[x][y]='#'; dfs(x+1,y,s); dfs(x,y+1,s); dfs(x-1,y,s); dfs(x,y-1,s); map[x][y]='-'; } int main() { // freopen("sousuo.txt","w",stdout); int T,n,m,i,j; scanf("%d",&T); while(T--) { memset(map,'#',sizeof(map)); scanf("%d%d",&n,&m); for(i=1;i<=n;++i) { getchar(); for(j=1;j<=m;++j) { map[i][j]=getchar(); if(map[i][j]=='S'){a=i;b=j;} if(map[i][j]=='E'){c=i;d=j;} } } p=11000; dfs(a,b,0); printf("%d\n",p); } return 0; }
C++ :
#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define min(x,y) x<y?x:y; bool flag; int x1,y1,x2,y2,a,b,m; char map[103][103]; void dfs(int i,int j,int cnt) { if(map[i][j]=='#') return ; if(i==x2&&j==y2) { m=min(cnt,m); flag= false; return ; } if(i>=1&&i<=a&&j>=1&&j<=b&&map[i][j]!='#') { cnt++; map[i][j]='#'; dfs(i,j-1,cnt); dfs(i-1,j,cnt); dfs(i,j+1,cnt); dfs(i+1,j,cnt); map[i][j]='-'; } } int main() { int T,i,j; cin>>T; while(T--) { m = 100000;flag = true; scanf("%d%d",&a,&b); for(i = 1 ; i <= a; i++) { for(j = 1 ; j <= b; j++) { cin>>map[i][j]; if(map[i][j]=='S') x1=i,y1=j; if(map[i][j]=='E') { x2=i,y2=j; } } } dfs(x1,y1,0); if(!flag) printf("%d\n",m); else printf("-1\n"); } return 0; }
Pascal :
program maze_problem; const dx:array[1..4]of integer=(0,1,0,-1); dy:array[1..4]of integer=(1,0,-1,0); var dui:array[1..10000,1..3]of integer; gr:array[1..200,1..200]of integer; i,j,k,n,x,y,fx,fy,nx,ny,t,times,m:integer; head,tail:integer; s:string; find:boolean; procedure count(x,y:integer); var i:integer; begin dui[head,1]:=x; dui[head,2]:=y; dui[head,3]:=1; while head<=tail do begin for i:=1 to 4 do begin nx:=dui[head,1]+dx[i]; ny:=dui[head,2]+dy[i]; if (nx>0)and(nx<=n)and(ny>0)and(ny<=m) then begin if gr[nx,ny]=0 then begin inc(tail); gr[nx,ny]:=1; dui[tail,1]:=nx; dui[tail,2]:=ny; dui[tail,3]:=dui[head,3]+1; if (nx=fx)and(ny=fy) then begin find:=true; times:=dui[tail,3]; exit; end;{then-final} end;{then-n} end;{then-nn} end;{for-i} inc(head); end{while} end;{count} procedure init; begin readln(t); for i:=1 to t do begin readln(n,m); fillchar(gr,sizeof(gr),0); for j:=1 to n do begin readln(s); for k:=1 to m do begin if s[k]='-' then gr[j,k]:=0; if s[k]='#' then gr[j,k]:=1; if s[k]='E' then begin fx:=j; fy:=k; gr[j,k]:=0; end;{then_E} if s[k]='S' then begin x:=j; y:=k; gr[j,k]:=1; end;{then-S} end;{for-k} end;{for-j} head:=1; tail:=1; find:=false; count(x,y); if find then writeln(times-1) else writeln('-1'); end;{for-i} end;{init} begin{main} init; end.
- 1
信息
- ID
- 650
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者