Advertisement
Josif_tepe

Untitled

Sep 22nd, 2024
110
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.29 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4.  
  5. char x[1005][1005];
  6. int visted[1005][1005];
  7. int y[1005][1005];
  8.  
  9. int main()
  10. {
  11.     int di[]={0,1,-1,0};
  12.     int dj[]={1,0,0,-1};
  13.     int t;
  14.     cin >> t;
  15.     for(int T = 0; T < t; T++) {
  16.         int n,m;
  17.         cin>>n>>m;
  18.        
  19.         for(int i = 0;i<n;i++){
  20.             for(int j = 0;j<m;j++){
  21.                 cin>>x[i][j];
  22.             }
  23.         }
  24.         for(int i = 0; i < 1004; i++) {
  25.             for(int j = 0; j < 1004; j++) {
  26.                 visted[i][j] = false;
  27.                 y[i][j] = 2e9;
  28.             }
  29.         }
  30.         int si = 0;
  31.         int sj = 0;
  32.         int ei = 0;
  33.         int ej = 0;
  34.         for(int i = 0;i<n;i++){
  35.             for(int j = 0;j<m;j++){
  36.                 if(x[i][j]=='E'){
  37.                     ei=i;
  38.                     ej=j;
  39.                 }
  40.                 if(x[i][j]=='S'){
  41.                     si=i;
  42.                     sj=j;
  43.                 }
  44.             }
  45.         }
  46.         int cekori = 0;
  47.         queue<int>bfs;
  48.         bfs.push(ei);
  49.         bfs.push(ej);
  50.         bfs.push(cekori);
  51.         while(!bfs.empty()){
  52.             int ci=bfs.front();
  53.             bfs.pop();
  54.             int cj=bfs.front();
  55.             bfs.pop();
  56.             int cekor=bfs.front();
  57.             bfs.pop();
  58.             y[ci][cj]=cekor;
  59.             for(int i=0;i<4;i++){
  60.                 int ti=ci+di[i];
  61.                 int tj=cj+dj[i];
  62.                 if(ti>=0 && ti<n && tj>=0 && tj<m && x[ti][tj]!='T' && visted[ti][tj]!=true){
  63.                     visted[ti][tj]=true;
  64.                     bfs.push(ti);
  65.                     bfs.push(tj);
  66.                     bfs.push(cekor+1);
  67.                 }
  68.             }
  69.         }
  70.         int dist = y[si][sj];
  71.         int dist2=0;
  72.         int cnt=0;
  73.         int hu=100;
  74.         for(int i = 0;i<n;i++){
  75.             for(int j = 0;j<m;j++){
  76.                 if(x[i][j] >= '1' && x[i][j]<='9'){
  77.                     dist2=y[i][j];
  78.                     if(dist2 <= dist) {
  79.                         int c = x[i][j] - '0';
  80.                         hu -= c;
  81.                     }
  82.                 }
  83.                
  84.             }
  85.         }
  86.        
  87.         if(hu<0){
  88.             cout<<0<<endl;
  89.         }else{
  90.             cout<<hu<<endl;
  91.         }
  92.     }
  93. }
  94.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement