結果

問題 No.13 囲みたい！
コンテスト
ユーザー myanta
提出日時 2017-04-30 23:26:36
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,536 bytes
コンパイル時間 1,314 ms
コンパイル使用メモリ 45,552 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-14 00:03:32
合計ジャッジ時間 3,353 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 RE * 15
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int remove_connection(int, int)’:
main.cpp:68:1: warning: no return statement in function returning non-void [-Wreturn-type]
   68 | }
      | ^
main.cpp: In function ‘int main()’:
main.cpp:112:38: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  112 |                                 scanf("%d", &f[y][x]);
      |                                 ~~~~~^~~~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#include<cstdio>
#include<vector>


using namespace std;


int w, h;
vector<vector<int> > f, c;


int calc_connection(void)
{
	int vx[]={ 1, 0,-1, 0};
	int vy[]={ 0,-1, 0, 1};
	int x, y, n, i, ret=0;

	for(y=1;y<=h;y++)
	{
		for(x=1;x<=w;x++)
		{
			if(f[y][x]==0) continue;

			c[y][x]=0;
			n=f[y][x];
			for(i=0;i<4;i++)
			{
				if(n==f[y+vy[i]][x+vx[i]])
				{
					c[y][x]++;
					ret=1;
				}
			}
			if(c[y][x]==0) f[y][x]=0;
		}
	}
	return ret;
}


int remove_connection(int x, int y)
{
	int vx[]={ 1, 0,-1, 0};
	int vy[]={ 0,-1, 0, 1};
	int i, n, nx, ny;

	n=f[y][x];
	for(;;)
	{
		c[y][x]--;
		if(c[y][x]<=0)
		{
			f[y][x]=0;
		}
		for(i=0;i<4;i++)
		{
			nx=x+vx[i];
			ny=y+vy[i];
			if(f[ny][nx]>0 && c[ny][nx]<2)
			{
				break;
			}
		}
		if(i>=4) break;
		x=nx;
		y=ny;
	}
}


int solve(void)
{
	int x, y, is_removed=1, ret=0;

	for(;is_removed;)
	{
		ret=calc_connection();
		is_removed=0;
		for(y=1;y<=h;y++)
		{
			for(x=1;x<=w;x++)
			{
				if(c[y][x]==1 && f[y][x]>0)
				{
					remove_connection(x, y);
					is_removed=1;
				}
			}
		}
	}
	return ret;
}

int main(void)
{
	int i, x, y;

	while(scanf("%d%d", &w, &h)==2)
	{
		f.clear();
		f.resize(h+2);
		for(i=0;i<f.size();i++)
		{
			f[i].resize(w+2);
		}
		c=f;

		for(y=1;y<=h;y++)
		{
			for(x=1;x<=w;x++)
			{
				scanf("%d", &f[y][x]);
			}
		}
		printf("%s\n", solve()?"possible":"impossible");
/*
		for(y=1;y<=h;y++)
		{
			for(x=1;x<=w;x++)
			{
				printf("%2d[%2d] ", f[y][x], c[y][x]);
			}
			printf("\n");
		}
		printf("\n");
*/
	}

	return 0;
}
0