글 읽기 - 반례가 뭘까요

noru0114 7년 전 0

어렵네요ㅠㅠ

고수분들 도와주세요

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <math.h>
#include <time.h>
#include <iostream>
#include <queue>
#include <stack>
#include <algorithm>
#include <deque>
#include <vector>
#include <utility>
#include <tuple>
#include <set>
#include <map>

using namespace std;

typedef struct
{
	int i;
	int j;
	int k;
	int count;
}node;

int board[1000][1000]={0};
int check[10][1000][1000];

int main(void)
{
	int n,m,k,i,j,t,res=-1,sw;
	int di[4]={0,0,1,-1};
	int dj[4]={1,-1,0,0};
	queue<node> q;
	node temp,tempp;
	scanf("%d%d%d",&n,&m,&k);
	for(i=0;i<n;i++)
		for(j=0;j<m;j++)
			scanf("%1d",&board[i][j]);
	for(i=0;i<n;i++)
		for(j=0;j<m;j++)
			for(t=0;t<10;t++)
				check[t][i][j]=-1;
	temp.i=0,temp.j=0,temp.k=0,temp.count=1;
	q.push(temp);
	check[0][0][0]=1;
	while(!q.empty())
	{
		temp=q.front();
		q.pop();
		if(temp.i==n-1 && temp.j==m-1)
		{
			if(res==-1)
				res=temp.count;
			else if(res>temp.count)
				res=temp.count;
		}
		for(i=0;i<4;i++)
			if(temp.i+di[i]>=0 && temp.i+di[i]<n && temp.j+dj[i]>=0 && temp.j+dj[i]<m && check[temp.k][temp.i+di[i]][temp.j+dj[i]]==-1)
			{
				sw=1;
				tempp.i=temp.i+di[i];
				tempp.j=temp.j+dj[i];
				tempp.k=temp.k;
				tempp.count=temp.count+1;
				if(board[tempp.i][tempp.j]==0)
				{
					for(j=0;j<tempp.k;j++)
						if(check[j][tempp.i][tempp.j]!=-1 && check[j][tempp.i][tempp.j]<=tempp.count)
						{
							sw=0;
							break;
						}
					if(sw==0)
						continue;
					q.push(tempp);
					check[tempp.k][tempp.i][tempp.j]=tempp.count;
				}
				else if(++tempp.k<=k)
				{
					for(j=0;j<tempp.k;j++)
						if(check[j][tempp.i][tempp.j]!=-1 && check[j][tempp.i][tempp.j]<=tempp.count)
						{
							sw=0;
							break;
						}
					if(sw==0)
						continue;
					q.push(tempp);
					check[tempp.k][tempp.i][tempp.j]=tempp.count;
				}
			}
	}
	printf("%d\n",res);
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례가 뭘까요

noru0114 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말