poj-3009-Curing 2.0

呂振麒 bio photo By 呂振麒 Comment

Curing 2.0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
using namespace std;
int M,N, arr[30][30], ans;
int ci, cj, act[4][2]={ {1,0},{0,1},{0,-1},{-1,0} }, de;
char ch[4] = {'D', 'R', 'L', 'U'};
inline bool ok(int i, int j){
  if(i>=N || j>=M || i<0 || j<0)return false;
  return true;
}
void dfs(int ii, int jj, int ts){
  if(ts == 10)return;
  int ci, cj;
  for(int i=0;i<4;i++){
    ci = ii+act[i][0], cj = jj+act[i][1];
    if(ok(ci, cj) && arr[ci][cj] == 1)
      continue;
    while(ok(ci, cj)){
      if(arr[ci][cj] == 1){
        arr[ci][cj] = 0;
        dfs(ci-act[i][0], cj-act[i][1], ts+1);
        arr[ci][cj] = 1;
        break;
      }
      if(arr[ci][cj] == 3){
        ans = min(ans, ts+1);
        return;
      }
    }
  }
  return;
}
int main(){
  while(cin>>M>>N && (N+M)){
    ans = 100;de=0;
    for(int i=0;i<N;i++)for(int j=0;j<M;j++){
      cin>>arr[i][j];
      if(arr[i][j] == 2)
        ci = i, cj = j, arr[i][j] = 0;
    }
    dfs(ci, cj, 0);
    cout<<(ans == 100 ? -1 : ans)<<endl;
  }
}
comments powered by Disqus