fork(1) download
copy 
  1. #include <iostream>
  2. #include <fstream>
  3. using namespace std;
  4.  
  5. int N,M,T,K, a[50][50],q[50*50][2],fx,fy, viz[50][50]; bool found;
  6.  
  7. void q_push(int x, int y){
  8.     q[++K][0]=x;
  9.     q[K][1]=y;
  10. }
  11.  
  12. bool valid(int x, int y){
  13.     if (x<1 || x>N || y<1 || y>M || a[x][y]==1 || viz[x][y]==1)
  14.         return 0;
  15.     return 1;
  16. }
  17.  
  18. void dfs(int x, int y){
  19.     if (valid(x,y)){
  20.         if (x==fx && y==fy)
  21.             found=1;
  22.  
  23.         if (a[x][y]==2 && !viz[x][y]){
  24.             viz[x][y]=2;
  25.             q_push(x,y);
  26.             return;
  27.         }
  28.  
  29.         viz[x][y]=1;
  30.         dfs(x+1,y);
  31.         dfs(x-1,y);
  32.         dfs(x,y+1);
  33.         dfs(x,y-1);
  34.     }
  35. }
  36.  
  37. bool possible(void){
  38.     int l=1,cost=0,i,aux;
  39.  
  40.     while(!found && cost<=T/2 && l<=K){
  41.         aux=K;
  42.         for (i=l; i<=aux; i++)
  43.             dfs(q[i][0],q[i][1]);
  44.         cost++;
  45.         l=aux+1;
  46.     }
  47.  
  48.     return (found);
  49. }
  50.  
  51. int main(){
  52.     cin >> N >> M >> T;
  53.  
  54.     int i,j; char c; bool f;
  55.     for (i=1; i<=N; i++)
  56.         for (j=1; j<=M; j++){
  57.             cin >> c;
  58.             if (c=='#')
  59.                 a[i][j]=1;
  60.             else if (c=='s')
  61.                 a[i][j]=2;
  62.             else if (c=='@')
  63.                 q_push(i,j);
  64.             else if (c=='x')
  65.                 fx=i,fy=j;
  66.         }
  67.  
  68.     f=possible();
  69.     if (f)
  70.         cout << "SUCCESS\n";
  71.     else
  72.         cout << "IMPOSSIBLE\n";
  73.  
  74.     return 0;
  75. }
  76.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/x7MYPB
problem , based on SPOJ submission 12441412 (C++ 4.3.2), 2014-09-23 21:03:08
language:
()
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!