1 solutions
-
0
C :
#include<stdio.h> #include<string.h> struct point{ int x,y; int step; }; int num_x[4]={0,-1,0,1}; int num_y[4]={-1,0,1,0}; char a[1005][1005]; struct point maps[1005*1005]; int main() { int n,i,j; int x1,y1,x2,y2; while(scanf("%d",&n)!=EOF){ memset(a,0,sizeof(a)); for(i=0;i<n;i++) scanf("%s",a[i]); scanf("%d%d%d%d",&x1,&y1,&x2,&y2); int head=1,rear=1; struct point st; st.x=x1;st.y=y1; st.step=0; a[x1-1][y1-1]='1'; maps[rear]=st; rear++; while(head!=rear){ struct point k=maps[head]; ++head; if(k.x==x2&&k.y==y2){ printf("%d\n",k.step); break; } for(i=0;i<4;++i){ struct point ss=k; ss.x=k.x+num_x[i]; ss.y=k.y+num_y[i]; if(a[ss.x-1][ss.y-1]=='0'&&ss.x<=n&&ss.x>0&&ss.y<=n&&ss.y>0){ ss.step=k.step+1; maps[rear]=ss; rear++; a[ss.x-1][ss.y-1]='1'; } } } } return 0; }C++ :
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define end END using namespace std; struct Node { int x,y; int s; }str,end; int n; int a[1201][1201],f[1201][1201]; const int dx[]={0,1,0,-1},dy[]={1,0,-1,0}; Node que[1201*1201]; void bfs(); void add(int x,int y,int s); int head=0,tail=1; int main() { cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)scanf("%1d",&a[i][j]); cin>>str.x>>str.y>>end.x>>end.y; str.s=0; f[str.x][str.y]=1; add(str.x,str.y,0); bfs(); //while(1); return 0; } void bfs() { while(head!=tail) { Node t=que[head]; for(int i=0;i<=3;i++) { int nx=t.x+dx[i]; int ny=t.y+dy[i]; if(nx>0&&ny<=n&&ny>0&&nx<=n&&a[nx][ny]==0) { Node k; if(f[nx][ny]==0) { if(nx==end.x&&ny==end.y) { printf("%d",t.s+1); return; } add(nx,ny,t.s+1); } } } head++; } } void add(int x,int y,int s) { Node k; k.x=x;k.y=y;k.s=s; que[tail++]=k; f[x][y]=1; }Pascal :
const dx:array[1..4]of shortint=(1,-1,0,0); dy:array[1..4]of shortint=(0,0,-1,1); var n,x1,y1,x2,y2:word; map:array[0..1001,0..1001]of char; que:array[1..1000000]of record x,y,dep:word; end; procedure init; var i,j:word; begin {assign(input,'save.in');reset(input); assign(output,'save.out');rewrite(output);} fillchar(map,sizeof(map),'1'); readln(n); for i:=1 to n do begin for j:=1 to n do read(map[i,j]); readln; end; readln(x1,y1,x2,y2); {close(input);} end;{init} procedure work; var head,tail:longword; i:byte; begin with que[1] do begin x:=x1; y:=y1; dep:=0; end; head:=0;tail:=1; repeat inc(head); for i:=1 to 4 do if(que[head].x+dx[i]>0)and(que[head].x+dx[i]<=n) and(que[head].y+dy[i]>0)and(que[head].y+dy[i]<=n) and(map[que[head].x+dx[i],que[head].y+dy[i]]='0')then begin inc(tail); with que[tail] do begin x:=que[head].x+dx[i]; y:=que[head].y+dy[i]; dep:=que[head].dep+1 end; map[que[tail].x,que[tail].y]:='1'; if(que[tail].x=x2)and(que[tail].y=y2)then begin writeln(que[tail].dep); close(output); halt; end; end; until head=tail; end;{work} begin{main} init; work; end.Java :
import java.util.ArrayList; import java.util.Scanner; public class Main { int n; char[][] map; int[] dx = {-1,1,0,0}, dy = {0,0,-1,1}; boolean[][] mark; public static void main(String[] args) { Main p = new Main(); } public Main() { Scanner sc = new Scanner(System.in); n = sc.nextInt();sc.nextLine(); map = new char[n][n]; mark = new boolean[n][n]; for (int i = 0; i < n ; i++) { String line = sc.nextLine(); map[i] = line.toCharArray(); } int start_x = sc.nextInt() - 1, start_y = sc.nextInt() - 1, end_x = sc.nextInt() - 1, end_y = sc.nextInt() - 1; bfs(start_x,start_y,end_x,end_y); } void bfs(int sx, int sy, int ex, int ey){ ArrayList<Node> queue = new ArrayList<>(); queue.add(new Node(sx,sy)); while (!queue.isEmpty()){ Node now = queue.remove(0); if(now.x == ex && now.y == ey) { System.out.println(now.step);return; } for (int i = 0; i < 4 ; i++) { int newx = now.x + dx[i], newy = now.y + dy[i]; if(newx>=0 && newx < n && newy >= 0 && newy < n && map[newx][newy] == '0' && !mark[newx][newy]) { queue.add(new Node(newx,newy,now.step+1)); mark[newx][newy] = true; } } } System.out.println("IMPOSSIBLE"); } class Node{ int x, y,step; public Node(int x, int y, int step) { this.x = x; this.y = y; this.step = step; } public Node(int x, int y) { this.x = x; this.y = y; } } }
- 1
Information
- ID
- 16771
- Time
- 1000ms
- Memory
- 128MiB
- Difficulty
- (None)
- Tags
- # Submissions
- 0
- Accepted
- 0
- Uploaded By