jzoj 1577. 【普及模拟】抓猫

lzusa 发布于 2019-03-20 1315 次阅读

 

题目描述

流浪猫布满城市的每一个角落，非常影响市容市貌，作为城市聘请的抓猫者，你有一种捕捉器，一定可以捕捉到所有走到里面的猫，更加幸运的是你有一个非常厉害的动物心理学家，他可以预测猫在不同位置的行走方向(共有东、西、南、北四种情况)

为了节约经费，问你最少需要多少个捕捉器才能把所有的猫都抓住。

 

输入

输入第一行包含两个整数N和M(1<=N,M<=1000),表示城市被划分成N×M的网格。接下来N行，每行包含M个字符“E”、“W”、“S”、“N”代表东、西、南、北4个方向，表示当猫在该位置的行走方向，保证猫不会走出城市区域。

输出

输出一个整数表示最少需要的捕捉器数。
就是沿着每一条路搜索，但是要注意结束条件是当前路没有被走过

 

var
  a:array[0..1000,0..1000] of char;
  f:array[0..1000,0..1000] of longint;
  i,j,k,n,m,s,p:longint;
  st:ansistring;
procedure dfs(x,y:longint);
var
  i,j,k:longint;
begin
  if f[x,y]>0 then
    begin
      if f[x,y]<>p then begin inc(p); exit; end;
      inc(s);
      inc(p);
      exit;
    end;
  if a[x,y]='W' then
    begin
      f[x,y]:=p;
      dfs(x,y-1);
    end
  else
  if a[x,y]='N' then
    begin
      f[x,y]:=p;
      dfs(x-1,y);
    end
  else
  if a[x,y]='S' then
    begin
      f[x,y]:=p;
      dfs(x+1,y);
    end
  else
  if a[x,y]='E' then
    begin
      f[x,y]:=p;
      dfs(x,y+1);
    end;
end;

begin
assign(input,'d.in');reset(input);
assign(output,'d.out');rewrite(output);
  readln(n,m);
  for i:=1 to n do
    begin
      readln(st);
      for j:=1 to m do
        a[i,j]:=st[j];
    end;
    p:=1;
  for i:=1 to n do
    for j:=1 to m do
    if f[i,j]=0 then
      dfs(i,j);
  writeln(s);
end.

 

]]>