1 条题解
-
0
C :
#include<stdio.h> int main(void) { int k,x; scanf("%d",&x); for(k=1;k<=x;k++) {int i,j,m,n,w,i1,i2,i3,j1,j2,j3,f=0,r=1; char mg[105][105]; int zg[105][105],ins[105][105],tx[4]={0,1,0,-1},ty[4]={1,0,-1,0},q[10005]; scanf("%d%d",&n,&m); getchar(); for(i=0;i<n;i++) { for(j=0;j<m;j++) scanf("%c",&mg[i][j]); getchar();} for(i=0;i<n;i++) for(j=0;j<m;j++) { zg[i][j]=0; ins[i][j]=0; if(mg[i][j]=='S') {i1=i;j1=j;} } q[f]=i1*m+j1; zg[i1][j1]=1; while(f<r) {w=q[f]; i2=w/m;j2=w%m; f++; for(i=0;i<4;i++) { i3=i2+tx[i];j3=j2+ty[i]; if(i3>=0&&i3<n&&j3>=0&&j3<m&&(mg[i3][j3]!='#')&&(!zg[i3][j3])) {zg[i3][j3]=1; ins[i3][j3]=ins[i2][j2]+1; q[r]=i3*m+j3; r++; } } } for(i=0;i<n;i++) for(j=0;j<m;j++) if(mg[i][j]=='E') if(ins[i][j]!=0) printf("%d\n",ins[i][j]); else printf("-1\n"); } return 0; }
C++ :
#include<iostream> #include<cstring> #include<queue> using namespace std; struct MAP { int x,y,step; }s,e,head,tail; char g[100][100]; int v[100][100],f[][2]={{-1,0},{0,1},{1,0},{0,-1}},n,m; int bfs() { memset(v,0,sizeof(v)); queue<struct MAP> q; q.push(s); s.step=0; v[s.x][s.y]=1; while(!q.empty()) { head=q.front(); q.pop(); for(int i=0;i<4;i++) { tail.x=head.x+f[i][0]; tail.y=head.y+f[i][1]; tail.step=head.step+1; if(!v[tail.x][tail.y]&&g[tail.x][tail.y]!='#'&&tail.x>=0&&tail.x<n&&tail.y>=0&&tail.y<m) { if(tail.x==e.x&&tail.y==e.y) return tail.step; v[tail.x][tail.y]=1; q.push(tail); } } } return -1; } int main() { int t,i,j; cin>>t; while(t--) { cin>>n>>m; for(i=0;i<n;i++) for(j=0;j<m;j++) { cin>>g[i][j]; if(g[i][j]=='S') { s.x=i; s.y=j; } else if(g[i][j]=='E') { e.x=i; e.y=j; } } cout<<bfs()<<endl; } return 0; }
Pascal :
var n,m,i,j,k,p,q,ii,nn:longint;x:string; f:array[0..101,0..101] of longint; ch:array[0..101,0..101] of char; procedure s(x:longint); var i,j:longint; begin if x>n*m then begin writeln('-1');exit;end; for i:=1 to n do for j:=1 to m do begin if f[i,j]=x then begin if ch[i-1,j]='-' then f[i-1,j]:=f[i,j]+1; if ch[i+1,j]='-' then f[i+1,j]:=f[i,j]+1; if ch[i,j-1]='-' then f[i,j-1]:=f[i,j]+1; if ch[i,j+1]='-' then f[i,j+1]:=f[i,j]+1; end; end; if f[p,q]<>0 then writeln(f[p,q]-1) else s(x+1); end; begin readln(nn); for ii:=1 to nn do begin readln(n,m); fillchar(f,sizeof(f),0); for i:=1 to n do begin readln(x); for j:=1 to m do begin ch[i,j]:=x[j]; if ch[i,j]='E' then begin ch[i,j]:='-'; p:=i; q:=j; end; if ch[i,j]='S' then f[i,j]:=1; end; end;s(1); end; end.
Java :
import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static int m,n; public static void main(String[] args) { Scanner in = new Scanner(System.in); int x = in.nextInt(); for(int ii=0;ii<x;ii++){ m = in.nextInt(); n = in.nextInt(); Node3 s = new Node3(); Node3 e = new Node3(); char[][] maze = new char[m][n]; for(int i=0;i<m;i++){ String str = in.next(); for(int j=0;j<n;j++){ maze[i][j] = str.charAt(j); if(maze[i][j]=='S'){ s.x=i; s.y=j; } else if(maze[i][j]=='E'){ e.x=i; e.y=j; } } } System.out.println(bfs(maze,s,e)); } } public static int bfs(char[][] maze, Node3 s, Node3 e) { int[][] d = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } }; Queue<Node3> q = new LinkedList<Node3>(); q.add(s); maze[s.x][s.y] = '@'; while (!q.isEmpty()) { Node3 t = q.poll(); for (int i = 0; i < 4; i++) { int xx = t.x + d[i][0]; int yy = t.y + d[i][1]; if (xx == e.x && yy == e.y){ return t.d+1; } } for (int i = 0; i < 4; i++) { int xx = t.x + d[i][0]; int yy = t.y + d[i][1]; if (xx >= 0 && xx < m && yy >= 0 && yy < n && maze[xx][yy] == '-') { maze[xx][yy] = '@'; q.add(new Node3(xx, yy, t.d + 1)); } } } return -1; } } class Node3{ int x,y,d; public Node3(){ d = 0; } public Node3(int a,int b,int c){ x = a; y = b; d = c; } }
Python :
# coding=utf-8 t=int(input()) for i in range(t): n,m=map(int,input().split()) mg=[] for i in range(n): h=[] hstr=input() for j in range(m): h.append(hstr[j]) mg.append(h) for i in range(n): for j in range(m): if mg[i][j]=="S": x_start,y_start=i,j dengdai=[[x_start,y_start,0]] fx=[[0,-1],[0,1],[-1,0],[1,0]] while dengdai: x,y,step=dengdai.pop(0) for x_y in fx: nx,ny=x+x_y[0],y+x_y[1] if 0<=nx<n and 0<=ny<m and mg[nx][ny]=="E": x,y,step=nx,ny,step+1 break elif 0<=nx<n and 0<=ny<m and mg[nx][ny]=="-": mg[nx][ny]=step+1 dengdai.append([nx,ny,step+1]) if mg[x][y]=="E": break if mg[x][y]=="E": print(step) else: print(-1)
- 1
信息
- ID
- 1459
- 时间
- 1000ms
- 内存
- 32MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者