jzoj 1577. 【普及模拟】抓猫

发布于 2019-03-20  906 次阅读


 

题目描述

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

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

 

输入

输入第一行包含两个整数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.

 

]]>