oj.uz

Submission #129768

# Submission time Handle Problem Language Result Execution time Memory
129768 2019-07-13T07:42:42 Z davitmarg Portals (BOI14_portals) C++17
20 / 100
 38 ms 30044 KB 
/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;

int n,m,k,st,en,used[1000006],dist[1000006];
pair<int,int> u[1003][1003],d[1003][1003],l[1003][1003],r[1003][1003];
vector<int> g[1000006];
char a[1003][1003];

int id(int y,int x)
{
	return y*m+x;
}

void print(int ind)
{
	int y,x;
    x=ind%m;
    if(!x)
		x=m;
    y=(ind-x)/m;
    cout<<"! "<<y<<" "<<x<<" d="<<dist[ind]<<endl;
}

void addNode(int a,int b)
{
    if(a==b)
		return;
	g[a].PB(b);
}

int main()
{
    cin >> n >> m;
    k=n*m;
    for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
            scanf(" %c",a[i]+j);
            if(a[i][j]=='S')
			{
				st=id(i,j);
                a[i][j]='.';
			}
			else if(a[i][j]=='C')
			{
				en=id(i,j);
                a[i][j]='.';
			}
		}
    for(int i=1;i<=n;i++)
        a[i][0]=a[i][m+1]='#';
    for(int i=1;i<=m;i++)
        a[0][i]=a[n+1][i]='#';


    for(int i=0;i<=n;i++)
		for(int j=0;j<=m;j++)
		{
            if(a[i][j]=='#')
                u[i][j]=l[i][j]=MP(i,j);
			else
			{
				u[i][j]=u[i-1][j];
				l[i][j]=l[i][j-1];
			}
		}

    for(int i=n+1;i>=1;i--)
		for(int j=m+1;j>=1;j--)
		{
            if(a[i][j]=='#')
                d[i][j]=r[i][j]=MP(i,j);
			else
			{
				d[i][j]=d[i+1][j];
				r[i][j]=r[i][j+1];
			}
		}

    for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			if(a[i][j]=='#')
                continue;
            if(a[i-1][j]!='#')
                addNode(id(i,j),id(i-1,j));
            if(a[i+1][j]!='#')
                addNode(id(i,j),id(i+1,j));
            if(a[i][j-1]!='#')
                addNode(id(i,j),id(i,j-1));
            if(a[i][j+1]!='#')
                addNode(id(i,j),id(i,j+1));

            if(a[i-1][j]=='#' || a[i+1][j]=='#' || a[i][j-1]=='#'|| a[i][j+1]=='#')
			{
				int y,x;
                y=u[i][j].first;
                x=u[i][j].second;
				addNode(id(i,j),id(y+1,x));

                y=d[i][j].first;
                x=d[i][j].second;
				addNode(id(i,j),id(y-1,x));

                y=l[i][j].first;
                x=l[i][j].second;
				addNode(id(i,j),id(y,x+1));

                y=r[i][j].first;
                x=r[i][j].second;
				addNode(id(i,j),id(y,x-1));
			}
		}

    queue<int> q;
    q.push(st);
    used[st]=1;
    while(!q.empty())
	{
		int v=q.front();
        q.pop();
        //print(v);
        for(int i=0;i<g[v].size();i++)
		{
			int to=g[v][i];
            if(used[to])
				continue;
			used[to]=1;
            dist[to]=dist[v]+1;
            q.push(to);
		}
	}

	cout<<dist[en]<<endl;

    return 0;
}


/*

4 4
S..#
....
....
..C.


*/

Compilation message

portals.cpp: In function 'int main()':
portals.cpp:144:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<g[v].size();i++)
                     ~^~~~~~~~~~~~
portals.cpp:59:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf(" %c",a[i]+j);
             ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 24 ms 24056 KB Output is correct
3 Correct 24 ms 24056 KB Output is correct
4 Correct 24 ms 23928 KB Output is correct
5 Correct 24 ms 24056 KB Output is correct
6 Correct 24 ms 24056 KB Output is correct
7 Correct 29 ms 24056 KB Output is correct
8 Correct 24 ms 24056 KB Output is correct
9 Correct 24 ms 23928 KB Output is correct
10 Incorrect 23 ms 23928 KB Output isn't correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23928 KB Output is correct
2 Correct 23 ms 24056 KB Output is correct
3 Correct 23 ms 24056 KB Output is correct
4 Correct 23 ms 23928 KB Output is correct
5 Correct 23 ms 24056 KB Output is correct
6 Correct 23 ms 24056 KB Output is correct
7 Correct 23 ms 24056 KB Output is correct
8 Correct 23 ms 24056 KB Output is correct
9 Correct 25 ms 24924 KB Output is correct
10 Incorrect 25 ms 24824 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23824 KB Output is correct
2 Correct 23 ms 24056 KB Output is correct
3 Correct 23 ms 24184 KB Output is correct
4 Correct 23 ms 24052 KB Output is correct
5 Correct 37 ms 29688 KB Output is correct
6 Correct 37 ms 29688 KB Output is correct
7 Correct 38 ms 30044 KB Output is correct
8 Correct 36 ms 29688 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 23 ms 24004 KB Output is correct
3 Correct 24 ms 24028 KB Output is correct
4 Correct 24 ms 23928 KB Output is correct
5 Correct 24 ms 24184 KB Output is correct
6 Correct 24 ms 24056 KB Output is correct
7 Correct 24 ms 24056 KB Output is correct
8 Correct 24 ms 23968 KB Output is correct
9 Correct 25 ms 24952 KB Output is correct
10 Incorrect 25 ms 24952 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 25 ms 24056 KB Output is correct
3 Correct 24 ms 24080 KB Output is correct
4 Correct 23 ms 23928 KB Output is correct
5 Correct 29 ms 24056 KB Output is correct
6 Correct 29 ms 24056 KB Output is correct
7 Correct 24 ms 24056 KB Output is correct
8 Correct 24 ms 24060 KB Output is correct
9 Correct 25 ms 24952 KB Output is correct
10 Incorrect 26 ms 24952 KB Output isn't correct
11 Halted 0 ms 0 KB -