Submission #1714068
Source Code Expand
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset> //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip> //do setprecision
#include <ctime>
#include <complex>
using namespace std;
#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)
#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double
const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;
int a[102][102]={};
int d[102][102]={};
int flag[102][102]={};
int sx=0,sy=0,tx=0,ty=0;
int main(){
int i,j,b, c,r,f=0;
char ch;
cin>>r>>c;
FORQ(i,1,r)FORQ(j,1,c){
cin>>ch;
d[i][j]=111111111;
a[i][j]=0;
flag[i][j]=0;
if(ch=='s'){
sx=i;sy=j;
d[i][j]=0;
}else if(ch=='t'){
tx=i;ty=j;
d[i][j]=1111111111;
}else{
a[i][j]=ch-'0';
}
}
while(flag[tx][ty]==0){
int min=1111111111;
int x=-1,y=-1;
FORQ(i,1,r)FORQ(j,1,c){
if(flag[i][j]==0&&min>d[i][j]){
min=d[i][j];
x=i;y=j;
}
}
flag[x][y]=1;
//f++;
//cout<<f<<" "<<x<<" "<<y<<endl;
if(x-1>=1){
if(d[x-1][y]>d[x][y]+a[x-1][y])d[x-1][y]=d[x][y]+a[x-1][y];
if(y+1<=c)if(d[x-1][y+1]>d[x][y]+a[x-1][y+1])d[x-1][y+1]=d[x][y]+a[x-1][y+1];
}
//x=x
if(y-1>=1)if(d[x][y-1]>d[x][y]+a[x][y-1])d[x][y-1]=d[x][y]+a[x][y-1];
if(y+1<=c)if(d[x][y+1]>d[x][y]+a[x][y+1])d[x][y+1]=d[x][y]+a[x][y+1];
//
if(x+1<=r){
if(d[x+1][y]>d[x][y]+a[x+1][y])d[x+1][y]=d[x][y]+a[x+1][y];
if(y+1<=c)if(d[x+1][y+1]>d[x][y]+a[x+1][y+1])d[x+1][y+1]=d[x][y]+a[x+1][y+1];
}
}
cout<<d[tx][ty]<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Office Ninja |
User |
kt_tenel |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2185 Byte |
Status |
WA |
Exec Time |
110 ms |
Memory |
512 KB |
Judge Result
Set Name |
All |
Score / Max Score |
0 / 100 |
Status |
|
Set Name |
Test Cases |
All |
001-sample-01.txt, 002-sample-02.txt, 003-minimum-01.txt, 004-random-01.txt, 005-random-02.txt, 006-random-03.txt, 007-random-04.txt, 008-random-05.txt, 009-random-06.txt, 010-random-07.txt, 011-random-08.txt, 012-random-09.txt, 013-random-10.txt, 014-random-11.txt, 015-random-12.txt, 016-random-13.txt, 017-random-14.txt, 018-random-15.txt, 019-random-16.txt, 020-random-17.txt, 021-random-18.txt, 022-random-19.txt, 023-random-20.txt, 024-maximum-01.txt, 025-maximum-02.txt, 026-maximum-03.txt, 027-maximum-04.txt, 999-handmade-01.txt |
Case Name |
Status |
Exec Time |
Memory |
001-sample-01.txt |
AC |
1 ms |
256 KB |
002-sample-02.txt |
AC |
1 ms |
256 KB |
003-minimum-01.txt |
AC |
1 ms |
256 KB |
004-random-01.txt |
WA |
4 ms |
256 KB |
005-random-02.txt |
WA |
4 ms |
256 KB |
006-random-03.txt |
WA |
4 ms |
384 KB |
007-random-04.txt |
WA |
2 ms |
256 KB |
008-random-05.txt |
WA |
51 ms |
384 KB |
009-random-06.txt |
WA |
1 ms |
256 KB |
010-random-07.txt |
WA |
3 ms |
256 KB |
011-random-08.txt |
WA |
2 ms |
384 KB |
012-random-09.txt |
WA |
5 ms |
384 KB |
013-random-10.txt |
WA |
2 ms |
256 KB |
014-random-11.txt |
WA |
18 ms |
384 KB |
015-random-12.txt |
WA |
2 ms |
256 KB |
016-random-13.txt |
AC |
2 ms |
256 KB |
017-random-14.txt |
WA |
23 ms |
256 KB |
018-random-15.txt |
WA |
2 ms |
384 KB |
019-random-16.txt |
WA |
16 ms |
384 KB |
020-random-17.txt |
WA |
2 ms |
256 KB |
021-random-18.txt |
WA |
5 ms |
384 KB |
022-random-19.txt |
WA |
23 ms |
384 KB |
023-random-20.txt |
WA |
2 ms |
256 KB |
024-maximum-01.txt |
WA |
110 ms |
384 KB |
025-maximum-02.txt |
WA |
108 ms |
512 KB |
026-maximum-03.txt |
WA |
92 ms |
384 KB |
027-maximum-04.txt |
WA |
24 ms |
384 KB |
999-handmade-01.txt |
AC |
65 ms |
384 KB |