글 읽기 - 반례 좀 찾아주세요

raby 4년 전 1

게시판에 올라온 모든 반례 다 넣어보고 제가 생각나는 예제들 모두 넣어봤는데도 반례를 도저히 못찾겠어요

제출하면 제출하자마자 바로 틀렸다고 나오는데 제발 도와주세요ㅠㅠ

#include <iostream>
#include <queue>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;
string s[1001];
int check_f[1001][1001], check_p[1001][1001];
int ax[]={1,0,-1,0}, ay[]={0,-1,0,1};
int w,h;
void bfs(queue<pair<int,int>>&q, int check[1001][1001]){
	while(!q.empty()){
		int y=q.front().first, x=q.front().second;
		q.pop();
		for(int i=0;i<4;i++){
			int ny=y+ay[i], nx=x+ax[i];
			if(ny>=0&&ny<h&&nx>=0&&nx<w){
				if(s[ny][nx]=='.'||s[ny][nx]=='@'){
					if(check[ny][nx]>-1){
						if(check[ny][nx]>check[y][x]+1){
							q.push(make_pair(ny,nx));
							check[ny][nx]=check[y][x]+1;
						}
					}
					else{
						q.push(make_pair(ny,nx));
						check[ny][nx]=check[y][x]+1;
					}
				}
			}
		}
	}
}
int main()
{
	int t;
	cin>>t;
	while(t--){
		cin>>w>>h;
		queue<pair<int,int>>f;
		queue<pair<int,int>>p;
		memset(check_f, -1, sizeof(check_f));
		memset(check_p, -1, sizeof(check_p));
		bool fire=0;
		for(int i=0;i<h;i++){
			cin>>s[i];
			for(int j=0;j<w;j++)
				if(s[i][j]=='*'){
					f.push(make_pair(i,j));
					check_f[i][j]++;
					fire=1;
				}
				else if(s[i][j]=='@'){
					p.push(make_pair(i,j));
					check_p[i][j]++;
				}
		}
		bfs(f,check_f);
		bfs(p,check_p);
		int r=1000000;
		for(int i=0;i<w;i++){
			if(check_p[0][i]>-1){
				if(!fire) r=min(r,check_p[0][i]);
				else if(check_p[0][i]<check_f[0][i])
					r=min(r,check_p[0][i]);
			}
			if(check_p[h-1][i]>-1){
				if(!fire) r=min(r,check_p[h-1][i]);
				else if(check_p[h-1][i]<check_f[h-1][i])
					r=min(r,check_p[h-1][i]);
			}
		}
		for(int i=0;i<h;i++){
			if(check_p[i][0]>-1){
				if(!fire) r=min(r,check_p[i][0]);
				else if(check_p[i][0]<check_f[i][0])
					r=min(r,check_p[i][0]);
			}
			if(check_p[i][w-1]>-1){
				if(!fire) r=min(r,check_p[i][w-1]);
				else if(check_p[i][w-1]<check_f[i][w-1])
					r=min(r,check_p[i][w-1]);
			}
		}
		if(r==1000000) cout<<"IMPOSSIBLE\n";
		else cout<<r+1<<'\n';
	}
}

raby 4년 전 9

찾았습니다

7 4

###.###

#.....#

#@....#

*######

일 경우 IMPOSSIBLE라고 뜨네요..

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

문제

문제

출처

ICPC

반례 좀 찾아주세요

raby 4년 전 1

raby 4년 전 9

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말