結果

問題 No.13 囲みたい！
ユーザー A8pfA8pf
提出日時 2018-10-05 13:27:42
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,281 bytes
コンパイル時間 729 ms
コンパイル使用メモリ 74,080 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-04-20 16:43:05
合計ジャッジ時間 1,225 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 WA -
testcase_04 AC 3 ms
6,944 KB
testcase_05 AC 27 ms
6,944 KB
testcase_06 WA -
testcase_07 AC 13 ms
6,940 KB
testcase_08 AC 4 ms
6,940 KB
testcase_09 AC 4 ms
6,940 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 3 ms
6,940 KB
testcase_12 AC 2 ms
6,940 KB
testcase_13 AC 2 ms
6,944 KB
testcase_14 AC 2 ms
6,940 KB
testcase_15 AC 1 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <utility>
#include <queue>
using namespace std;

typedef long long ll;
ll MOD = 1e9+7;

int m[100][100];
int w,h;

int bfs(int si,int sj,int ti,int tj,int n)
{
	bool check[100][100];
	fill(check[0],check[100],false);
	deque<pair<int,int>> q;
	pair<int,int> goal=make_pair(ti,tj);
	check[si][sj]=true;
	//隣接するt以外の頂点を最初にキューに入れる
	//上下左右を探索
	int x=sj;
	int y=si;
	if(x<w-1 && m[y][x+1]==n && make_pair(y,x+1)!=goal)
	{
		check[y][x+1]=true;
		q.push_back(make_pair(y,x+1));
	}
	if(x>0 && m[y][x-1]==n && make_pair(y,x-1)!=goal)
	{
		check[y][x-1]=true;
		q.push_back(make_pair(y,x-1));
	}
	if(y<h-1 && m[y+1][x]==n && make_pair(y+1,x)!=goal)
	{
		check[y+1][x]=true;
		q.push_back(make_pair(y+1,x));
	}
	if(y<h+1 && m[y-1][x]==n && make_pair(y-1,x)!=goal)
	{
		check[y-1][x]=true;
		q.push_back(make_pair(y-1,x));
	}
	//ここからBFS
	while(!q.empty())
	{
		pair<int,int> v=q.front();
		x=v.second;
		y=v.first;
		q.pop_front();
		if(v==goal)
		{
			return 1;
		}
		//上下左右を探索
		if(x<w-1 && m[y][x+1]==n && !check[y][x+1])
		{
			check[y][y+1]=true;
			q.push_back(make_pair(y,x+1));
		}
		if(x>0 && m[y][x-1]==n && !check[y][x-1])
		{
			check[y][x-1]=true;
			q.push_back(make_pair(y,x-1));
		}
		if(y<h-1 && m[y+1][x]==n && !check[y+1][x])
		{
			check[y+1][x]=true;
			q.push_back(make_pair(y+1,x));
		}
		if(y<h+1 && m[y-1][x]==n && !check[y-1][x])
		{
			check[y-1][x]=true;
			q.push_back(make_pair(y-1,x));
		}
	}
	return 0;
}

int main()
{
	int ans=0;
	cin>>w>>h;
	for(int i=0;i<h;i++)
	{
		for(int j=0;j<w;j++)
			cin>>m[i][j];
	}

	//始点を探索する
	for(int i=0;i<h;i++)
	{
		for(int j=0;j<w;j++)
		{
			//隣接する同じ数字の組み合わせを探し、それぞれにBFS
			if(i>0 && m[i][j]==m[i-1][j])
				ans+=bfs(i,j,i-1,j,m[i][j]);
			if(i<h-1 && m[i][j]==m[i+1][j])
				ans+=bfs(i,j,i+1,j,m[i][j]);
			if(j>0 && m[i][j]==m[i][j-1])
				ans+=bfs(i,j,i,j-1,m[i][j]);
			if(j<w-1 && m[i][j]==m[i][j-1])
				ans+=bfs(i,j,i,j-1,m[i][j]);
			if(ans>0)
			{
				//cerr<<n<<" "<<j<<" "<<i<<endl;
				cout<<"possible"<<endl;
				return 0;
			}
		}
	}
	cout<<"impossible"<<endl;
	return 0;
}
0